Euler Totient Function φ(n)

Euler's totient function

Euler's totient φ(n) counts the integers in [1, n] that are coprime with n — that is, share no prime factor with it. For a prime p, every smaller positive integer is coprime, so φ(p) = p − 1. The function is multiplicative: if n = p₁^a₁ · p₂^a₂ · … is the prime factorisation, then φ(n) = n · ∏(1 − 1/pᵢ). Examples: φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 4 (the integers 1, 5, 7, 11). For two distinct primes p ≠ q, φ(p · q) = (p − 1)(q − 1) — the identity at the heart of RSA. Euler's theorem generalises Fermat's little theorem: a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1.

Where the totient shows up

• RSA — key generation picks primes p, q, computes n = p · q and φ(n) = (p − 1)(q − 1), then derives the private exponent d ≡ e^(−1) (mod φ(n)).
• Order of elements in the multiplicative group (ℤ/nℤ)* — which has exactly φ(n) elements.
• ElGamal and other discrete-log cryptosystems rely on the group structure that the totient describes.
• Counting reduced fractions with denominator n in lowest terms — there are exactly φ(n) of them.

FAQ

Why is φ(n) hard to compute without knowing the factorisation? Because it requires the prime factors of n. Recovering φ(n) from n alone is equivalent to factoring n — and is what makes RSA secure.

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

Is the totient always even for n > 2? Yes — every n > 2 has at least one factor of (p − 1) with p odd or contributes 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 used in modern RSA implementations instead of φ.