Euler's totient function explained
Write down the numbers from 1 to 10 and strike out every one that shares a factor with 10. Four are left: 1, 3, 7 and 9. That count, φ(10) = 4, is Euler's totient, one of the most used functions in number theory, from fractions and clocks to the encryption that protects online payments.
Counting coprime numbers
Two numbers are coprime when their greatest common divisor is 1. φ(n) counts the k from 1 to n with gcd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 and φ(1) = 1. The same count turns up in many places. It is the number of fractions k/n between 0 and 1 that are already in lowest terms, the number of step sizes that take a hand round an n-hour clock through every hour, and the number of k that have an inverse mod n, so that k × x ≡ 1 (mod n) can be solved.
The product formula
If the primes dividing n are p₁, p₂ …, then φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. The reason is a sieve. Half of all numbers are even, so taking out the multiples of 2 leaves the fraction 1 − 1/2; of the numbers left, one in three is a multiple of 3, and so on. By the Chinese remainder theorem the conditions for different primes are independent, so the fractions simply multiply. For 100 = 2² × 5² that gives 100 × 1/2 × 4/5 = 40. Two facts give the same result in another form: φ(p^k) = p^(k−1)(p − 1), and φ(mn) = φ(m) φ(n) when m and n are coprime, so φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Euler's theorem
Fermat noticed in 1640 that a^(p−1) ≡ 1 (mod p) for a prime p and any a that p does not divide. Euler proved the general version, published in 1763: a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1. The proof is short. Multiply the φ(n) numbers coprime to n by a; the products are again coprime to n and all different mod n, so they are the same numbers in another order, and comparing the two products leaves a^φ(n) ≡ 1. The smallest exponent that works for a given a is its order, which always divides φ(n); the smallest that works for every a at once is Carmichael's function λ(n). For 561 = 3 × 11 × 17, λ(561) = 80 divides 560, so a^560 ≡ 1 (mod 561) for every a coprime to 561 although 561 is not prime. It is the smallest Carmichael number, and the reason Fermat's test alone cannot prove that a number is prime.
Gauss's divisor sum and the average
Add φ(d) over the divisors d of n and you always get n back: for 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss proved it in his Disquisitiones Arithmeticae of 1801; one way to see it is to write the fractions 1/12, 2/12 … 12/12 in lowest terms and sort them by their denominators. On average φ(k) is about 0.61 k: the mean of φ(k)/k tends to 6/π² ≈ 0.6079, which is also the probability that two random whole numbers are coprime, and φ(1) + … + φ(N) is close to 3N²/π². For N = 1,000 the sum is 304,192, against 3N²/π² ≈ 303,964.
Values that never occur
φ(n) is even for every n from 3 on, because the numbers coprime to n come in pairs k and n − k. Not every even number is a totient either: 14, 26, 34, 38 and 50 are the first that never occur, while 24 is φ of ten different numbers, from 35 to 90. Finding them is a finite search, since every prime p that divides n must have p − 1 dividing φ(n). In 1907 Robert Carmichael claimed that no value is taken exactly once. His proof was wrong, the claim is still open, and any exception would have to be larger than 10^(10^10). D. H. Lehmer asked in 1932 whether φ(n) can divide n − 1 for a composite n; no example is known.
Totients in RSA
RSA picks two large primes p and q and publishes n = pq and an exponent e. Because φ(n) = (p − 1)(q − 1), whoever can factor n can compute φ(n), and from it the private exponent d with e × d ≡ 1 (mod φ(n)); Euler's theorem then makes (m^e)^d ≡ m (mod n). In the textbook example n = 3233 = 61 × 53, φ(n) = 3,120, e = 17 and d = 2,753. Many implementations use λ(n) = lcm(p − 1, q − 1) instead, here 780, which gives the smaller d = 413. Computing φ(n) for an RSA modulus with 600 digits is as hard as factoring it: from n and φ(n) the two primes follow with one square root.
Explore it
Open the calculator and enter any n up to 10^18 to see φ(n) with its prime factors and the formula. Up to 500 the numbers 1 to n are drawn, the coprime ones filled in and the others coloured by the smallest prime they share with n, so the product formula becomes a sieve you can count. Pick a number a to check Euler's theorem, switch to Plot to see φ(k) up to 100,000 with the primes on the line φ(p) = p − 1, or to Inverse to find every n with φ(n) = m.
Frequently asked questions
Why is φ(1) = 1?
Because gcd(1, 1) = 1: the only number from 1 to 1 is coprime to 1. The convention also keeps the formulas working, for example Gauss's sum over the divisors of n, which for n = 1 is just φ(1) = 1.
Is φ the same as the prime counting function?
No. π(n) counts the primes up to n, φ(n) the numbers up to n that are coprime to n. φ(10) = 4 counts 1, 3, 7 and 9, while π(10) = 4 counts 2, 3, 5 and 7. They agree there by coincidence: φ(12) = 4, but π(12) = 5.
How fast can φ(n) be computed?
As fast as n can be factored. With the prime factors known it takes a few multiplications; without them no fast method is known, which is what RSA relies on. For numbers up to 10^18 factoring takes milliseconds in a browser, for numbers with hundreds of digits it can take years.
Which numbers have the smallest φ(n) compared to n?
Numbers with many small prime factors. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… depends only on which primes divide n, not on their powers: for every power of 2 it is exactly 1/2, and for 30 = 2 × 3 × 5 it is 8/30, about 27 %. The product of the first 15 primes, 614,889,782,588,491,410, has φ(n)/n ≈ 14 %, the lowest of any number up to 10^18.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the totient calculator