Euler's Totient Function
The function φ(n) counting the integers between 1 and n that are coprime to n, a cornerstone of modular arithmetic and the basis of RSA encryption.
Euler's totient function φ(n) counts how many integers in the range 1 to n are coprime to n — that is, share no prime factor with n. For example, φ(10) = 4 because 1, 3, 7, and 9 are the four numbers below 10 with no common factor with 10. The function was introduced by Leonhard Euler in the 18th century and is a central object in number theory: it counts the units of modular arithmetic, the residues that have multiplicative inverses modulo n.
For a prime p, every number from 1 to p−1 is coprime to p, so φ(p) = p − 1. For a power of a prime, φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ(1 − 1/p). The function is multiplicative in the sense that φ(ab) = φ(a)φ(b) whenever a and b are coprime, and combining these facts gives the general formula from the prime factorization n = p₁ᵉ¹p₂ᵉ²…: φ(n) = n(1 − 1/p₁)(1 − 1/p₂)… . So φ(12) = 12(1 − 1/2)(1 − 1/3) = 4.
The deep reason the totient matters is Euler's theorem: if a and n are coprime, then a^φ(n) ≡ 1 (mod n). This generalizes Fermat's little theorem (the p − 1 special case) and is the engine of modular exponentiation shortcuts. In public-key cryptography, RSA picks two large primes p and q, sets n = pq, and uses φ(n) = (p − 1)(q − 1) to build the public and private exponents: messages are encrypted as mᵉ mod n and decrypted as cᵈ mod n, and Euler's theorem is what guarantees the two operations cancel. An attacker who could compute φ(n) could break RSA, but computing φ(n) requires factoring n — which is why factoring difficulty is the security of the scheme.
Tags
cryptography euler modular arithmetic number theory