Euler's Totient Function φ(n)

Euler's totient φ(n)

Euler's totient φ(n) tells you how many integers in [1, n] are coprime with n, meaning they share no prime factor with it. Take a prime p: every smaller positive integer is coprime to it, so φ(p) = p − 1. The function is also multiplicative. When gcd(m, n) = 1, you get φ(m · n) = φ(m) · φ(n). Starting from the prime factorisation n = p₁^a₁ · p₂^a₂ · …, the closed form follows: φ(n) = n · ∏(1 − 1/pᵢ). So φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 4, which are the integers 1, 5, 7, 11. With two distinct primes it collapses to φ(p · q) = (p − 1)(q − 1), the identity RSA is built on. And Euler's theorem extends Fermat's little theorem: a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1.

Where the totient shows up

• RSA — key generation computes φ(n) = (p − 1)(q − 1) so it can derive the private exponent d ≡ e^(−1) (mod φ(n)).
• Chinese Remainder Theorem (CRT) — speeds up RSA decryption by handling the math modulo p and q on their own.
• Multiplicative order — the order of any element in (ℤ/nℤ)* always divides φ(n).
• ECDSA and discrete-log systems lean on the totient to describe how big cyclic groups are.

FAQ

Why is φ(n) hard to compute without the factorisation? Pulling φ(n) out of n by itself turns out to be as hard as factoring n, which is the very problem that keeps RSA secure.

What is φ(1)? By convention φ(1) = 1: the only integer in [1, 1] is 1, and gcd(1, 1) = 1.

Is φ(n) always even for n > 2? Yes — there is always either an odd prime factor contributing (p − 1) or a factor of 2 from 2^k.

How does it relate to Carmichael's function? Carmichael's λ(n) is the smallest exponent for which a^λ(n) ≡ 1; it always divides φ(n) and is often preferred in modern RSA implementations.