Euler’s Totient Function Calculator φ(n)
Compute Euler’s totient function φ(n): prime factorization, formula breakdown, list of integers coprime to n, and a table of φ(k) values. Includes step-by-step explanation and number theory notes.
Full original guide (expanded)
Euler’s Totient Function Calculator φ(n)
Number of integers ≤ n that are coprime to nCompute Euler’s totient function φ(n) for a positive integer n. See the prime factorization of n, a step-by-step formula breakdown, and (for smaller n) the full list of integers between 1 and n that are coprime to n.
Typical use cases: number theory, modular arithmetic, RSA and public-key cryptography, contest problems, and teaching arithmetic functions.
1. Enter n and options
The calculator is optimised for n up to about 109 using trial division. Very large n may be slow to factor.
φ(n) is always an integer; decimals only affect intermediate ratios.
2. Results for your n
3. φ(k) table for 1 ≤ k ≤ N
Generate a small table of totient values to see patterns (for example φ(p) = p − 1 for primes, or multiplicative behaviour).
The table lists k and φ(k) for 1 ≤ k ≤ N.
Tip: try N = 30 to see how often φ(k) is even, and how values behave for primes vs composite numbers.
| k | φ(k) | Prime factorization |
|---|
Definition of Euler’s totient function
For a positive integer \(n\), Euler’s totient function \(\varphi(n)\) (also written \(\phi(n)\)) is defined as:
\[ \varphi(n) = \#\{\,k \in \mathbb{Z} : 1 \le k \le n,\ \gcd(k,n) = 1\,\}, \]
i.e. the number of integers between 1 and n that are coprime to n.
Example: for \(n = 10\), the numbers between 1 and 10 that are coprime to 10 are \(1, 3, 7, 9\), so \(\varphi(10) = 4\).
Prime factorization formula
If the prime factorization of \(n\) is \[ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \] where the \(p_i\) are distinct primes, then Euler’s formula states:
\[ \varphi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right) = p_1^{a_1-1}(p_1 - 1)\cdot p_2^{a_2-1}(p_2 - 1)\cdots p_k^{a_k-1}(p_k - 1). \]
This shows that \(\varphi\) is a multiplicative arithmetic function: if \(\gcd(m,n)=1\), then \(\varphi(mn) = \varphi(m)\varphi(n)\).
Example: φ(36)
Let’s compute \(\varphi(36)\) step by step:
- Factor 36: \(36 = 2^2 \cdot 3^2\).
- Distinct primes are \(2\) and \(3\).
- Apply Euler’s formula: \[ \varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12. \]
- Check by counting: the integers between 1 and 36 that are coprime with 36 are 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 and 35 – exactly 12 numbers.
Connections and applications
Euler’s theorem and RSA
Euler’s totient function appears in Euler’s theorem:
If \(\gcd(a,n)=1\), then \[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]
When \(n = p\) is prime, \(\varphi(p) = p - 1\) and Euler’s theorem reduces to Fermat’s little theorem. In the RSA cryptosystem, if \(n = pq\) with distinct primes \(p\) and \(q\), then \(\varphi(n) = (p-1)(q-1)\), and the secret decryption exponent is chosen using this φ(n).
Basic properties of φ(n)
- \(\varphi(1) = 1\).
- For a prime \(p\), \(\varphi(p) = p - 1\).
- For a prime power \(p^k\), \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)\).
- If \(\gcd(m, n) = 1\), then \(\varphi(mn) = \varphi(m)\varphi(n)\).
- For \(n > 2\), \(\varphi(n)\) is even (since numbers occur in pairs modulo n).
FAQ: using this totient calculator
Why do you need the factorization of n?
The direct definition of \(\varphi(n)\) via gcd counts is straightforward but inefficient for large n: you would need to compute \(\gcd(k,n)\) for many k. Using the prime factorization and Euler’s formula is much faster and reveals the structure of φ(n). That is why the calculator first factors n.
What happens for very large n (e.g. RSA-sized moduli)?
For cryptographic-size n (hundreds or thousands of bits), factoring n is deliberately hard – this is what RSA security relies on. Our calculator uses naive trial division, so it is suited to educational and moderate-size examples, not to breaking cryptographic keys. For huge n, you must already know the prime factors in order to compute φ(n).
Can I rely on this tool for proofs?
This calculator is designed as a learning and exploration tool. It implements the standard totient formulas, but for formal proofs, contest submissions or research you should always back up numerical evidence with rigorous number-theoretic arguments.
Formula (LaTeX) + variables + units
\varphi(n) = \#\{\,k \in \mathbb{Z} : 1 \le k \le n,\ \gcd(k,n) = 1\,\},
n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},
\varphi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right) = p_1^{a_1-1}(p_1 - 1)\cdot p_2^{a_2-1}(p_2 - 1)\cdots p_k^{a_k-1}(p_k - 1).
\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12.
a^{\varphi(n)} \equiv 1 \pmod{n}.
','\
\[ \varphi(n) = \#\{\,k \in \mathbb{Z} : 1 \le k \le n,\ \gcd(k,n) = 1\,\}, \] i.e. the number of integers between 1 and n that are coprime to n.
\[ \varphi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right) = p_1^{a_1-1}(p_1 - 1)\cdot p_2^{a_2-1}(p_2 - 1)\cdots p_k^{a_k-1}(p_k - 1). \]
If \(\gcd(a,n)=1\), then \[ a^{\varphi(n)} \equiv 1 \pmod{n}. \]
- No variables provided in audit spec.
- NIST — Weights and measures — nist.gov · Accessed 2026-01-19
https://www.nist.gov/pml/weights-and-measures - FTC — Consumer advice — consumer.ftc.gov · Accessed 2026-01-19
https://consumer.ftc.gov/
Last code update: 2026-01-19
- Initial audit spec draft generated from HTML extraction (review required).
- Verify formulas match the calculator engine and convert any text-only formulas to LaTeX.
- Confirm sources are authoritative and relevant to the calculator methodology.