One deceptively simple question — how many numbers below n share no factor with it? — turns out to govern the structure of modular arithmetic, generalize Fermat's little theorem, and sit at the mathematical heart of RSA encryption.
Two integers are coprime (or relatively prime) when their greatest common divisor is 1 — they share no prime factor. Euler's totient function φ(n) counts how many of the integers 1, 2, …, n are coprime to n.
Take n = 12. Its prime factors are 2 and 3, so we strike out every multiple of 2 and every multiple of 3:
survivors: 1, 5, 7, 11 → φ(12) = 4
Only 1, 5, 7, 11 survive, so φ(12) = 4. These four survivors are not just a curiosity — they are exactly the residues that have multiplicative inverses mod 12, and they form a group under multiplication: the group of units (ℤ/12ℤ)×. The totient is that group's size. This is the deeper reason φ keeps appearing: it measures how much genuine multiplicative structure lives inside arithmetic mod n.
Convention
φ(1) = 1, since gcd(1, 1) = 1. And for any prime p, every one of 1, …, p − 1 is coprime to p, so φ(p) = p − 1 — the largest the totient can ever be relative to n.
Modular arithmetic lives naturally on a circle: the residues 1 through n arranged like marks on a clock face. Drag the slider and watch which residues light up brass — those are the ones coprime to n. Their count is φ(n).
Notice the patterns: primes light up everything except the top mark; even numbers immediately extinguish half the ring; and highly composite values like 30 or 60 leave surprisingly few survivors.
Among 1, …, pk, the only numbers not coprime to pk are the multiples of p, and there are exactly pk−1 of them. Everything else survives:
example: φ(8) = 8 − 4 = 4 · the survivors are 1, 3, 5, 7
If gcd(m, n) = 1, then
This is a direct consequence of the Chinese Remainder Theorem: a residue mod mn corresponds to a pair of residues (one mod m, one mod n), and it's a unit exactly when both components are units. The unit group factors, so its size multiplies. Caution: the coprimality condition is essential — φ(4) = 2 but φ(2)·φ(2) = 1.
Combine the first two rules across the prime factorization n = p₁a₁ p₂a₂ ⋯ prar and the whole thing telescopes into one elegant expression:
Read it as a sieve: start with all n residues, throw away the fraction 1/p that each prime divisor claims, and what remains is φ. Each prime is "charged" only once, no matter its exponent.
Factor first: 360 = 2³ · 3² · 5. Then:
Or via prime powers and multiplicativity: φ(8)·φ(9)·φ(5) = 4 · 6 · 4 = 96. Same answer, as it must be.
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| φ(n) | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
The sequence looks erratic — it is famously not monotonic — but every value is fully determined by the prime factorization. That tight coupling between φ(n) and factoring is exactly what cryptography exploits.
Euler introduced φ in 1763 to generalize Fermat's little theorem beyond prime moduli. The result:
Euler's Theorem (1763)
If gcd(a, n) = 1, then aφ(n) ≡ 1 (mod n).
Why it's true, in one paragraph. The units mod n form a group of order φ(n). Multiplying every unit by a just permutes them, so the product of all units is unchanged — which forces aφ(n) = 1 in the group. (Equivalently: by Lagrange's theorem, every element's order divides the group's order.)
Setting n = p prime recovers Fermat's little theorem, since φ(p) = p − 1:
RSA rests on a beautiful asymmetry involving the totient:
The key pair is built from φ: choose a public exponent e coprime to φ(n), and compute the private exponent d ≡ e−1 (mod φ(n)). Then for a message m:
encryption then decryption returns the message — courtesy of Euler's theorem
The private key works because ed ≡ 1 (mod φ(n)), so the exponent collapses via aφ(n) ≡ 1. An 18th-century counting function turned out to be the hinge of internet security. (In practice, implementations use the Carmichael function λ(n) = lcm(p−1, q−1), a refinement of φ that gives the smallest universal exponent — the principle is identical.)
Two implementations: the transparent definition-based count, and the fast product-formula version built on factor(). Then a numerical check of Euler's theorem.
% --- totient_naive.m : straight from the definition --- function t = totient_naive(n) t = sum(gcd(1:n, n) == 1); end % --- totient_fast.m : Euler's product formula --- function t = totient_fast(n) p = unique(factor(n)); % distinct prime divisors t = n * prod(1 - 1 ./ p); % n * prod(1 - 1/p) t = round(t); % clean up float dust end % --- sanity checks --- totient_fast(12) % ans = 4 totient_fast(360) % ans = 96 arrayfun(@totient_naive, 1:12) % 1 1 2 2 4 2 6 4 6 4 10 4 % --- verify Euler's theorem: a^phi(n) ≡ 1 (mod n) --- n = 360; a = 7; % gcd(7,360) = 1 powermod = @(a,e,n) mod_pow(a,e,n); % see below function r = mod_pow(a, e, n) % square-and-multiply r = 1; a = mod(a, n); while e > 0 if mod(e, 2) == 1, r = mod(r*a, n); end a = mod(a*a, n); e = floor(e/2); end end mod_pow(7, totient_fast(360), 360) % ans = 1 ✓ Euler
Try arrayfun(@totient_fast, 1:100) and plot it — the scatter shows the p − 1 ceiling traced by the primes and the sparse floors carved out by highly composite numbers.