What is Euler’s totient function φ(n)?

Euler’s totient function φ(n) is the number of positive integers between 1 and n that are coprime to n, i.e. that share no common prime factor with n. For example, φ(10) = 4 because only 1, 3, 7 and 9 are coprime to 10.

How is φ(n) computed from the prime factorization of n?

If the prime factorization of n is n = p1^a1 · p2^a2 · … · pk^ak, then Euler’s formula states that φ(n) = n · ∏(1 − 1/pi), where the product runs over the distinct prime divisors of n. The calculator uses this multiplicative formula after factoring n into its prime factors.

Why is Euler’s totient function important in cryptography?

Euler’s totient function plays a central role in public-key cryptography, particularly in the RSA algorithm. If n = pq is the product of two distinct primes, then φ(n) = (p − 1)(q − 1). Euler’s theorem, a generalisation of Fermat’s little theorem, states that for any integer a coprime to n, a^{φ(n)} ≡ 1 (mod n). RSA relies on the difficulty of computing φ(n) without knowing the factorization of n.

Why can’t the calculator list all coprimes for very large n?

The count φ(n) can be very large. Listing all integers between 1 and n that are coprime to n would be impractical for large n because it requires scanning many values and would produce extremely long output. For that reason the calculator only shows the explicit list of coprimes when n is below a configurable threshold (for example n ≤ 2000), and otherwise reports only the count.

Does the calculator handle non-integer or negative inputs?

By definition Euler’s totient function is used for positive integers. The calculator validates the input and restricts it to integers n ≥ 1. If you enter a non-integer, negative or extremely large value, you will see a validation message instead of a totient result.

Euler’s Totient Function Calculator – φ(n), Prime Factorization & Coprime Integers

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.

Euler’s Totient Function Calculator φ(n)

1. Enter n and options

2. Results for your n

3. φ(k) table for 1 ≤ k ≤ N