Number Theory
Euler's Totient Function – Counting Coprime Numbers
Euler's totient function, written φ(n), counts how many whole numbers from 1 to n share no common factor with n other than 1 (that is, how many are coprime to n). It looks like a simple counting exercise, but it turns out to be exactly the missing ingredient needed to generalise Fermat's Little Theorem – and, centuries later, to build RSA encryption.
Leonhard Euler introduced the function in 1763 as part of his work generalising Fermat's Little Theorem to any modulus, not just primes. Euler used his own notation for the function; the now-familiar Greek letter φ (phi) was introduced later by Gauss. Together, Euler's 1736 and 1763 papers established what is now called Euler's theorem: for any integers a and n with gcd(a, n) = 1, aφ(n) ≡ 1 (mod n) – a direct extension of Fermat's Little Theorem to composite moduli.
Computing φ(n)
For a prime p, every one of the numbers 1 to p−1 is automatically coprime to p, so φ(p) = p − 1.
Checking 1 to 9 against 9: 1, 2, 4, 5, 7, 8 share no factor with 9 (3, 6, 9 do, since they share the factor 3).
That's 6 numbers, so φ(9) = 6.
The Multiplicative Formula
For distinct primes p and q: φ(pq) = (p − 1)(q − 1)
More generally, φ is multiplicative: φ(mn) = φ(m)φ(n) whenever m and n share no common factor.
10 = 2 × 5, and 2, 5 are distinct primes.
φ(10) = (2 − 1)(5 − 1) = 1 × 4 = 4.
Euler's Theorem and RSA
Euler's theorem – aφ(n) ≡ 1 (mod n) – is exactly the mathematical fact that makes RSA encryption work. RSA sets n = pq, the product of two large secret primes, and relies entirely on φ(n) = (p − 1)(q − 1) to build its encryption and decryption keys. See our Number Theory in Cryptography page for the full picture.
Key Takeaways
- φ(n) counts the integers from 1 to n that are coprime to n.
- For prime p, φ(p) = p − 1.
- For distinct primes p and q, φ(pq) = (p − 1)(q − 1).
- Euler's theorem aφ(n) ≡ 1 (mod n) generalises Fermat's Little Theorem and underlies RSA encryption.