Euler's Totient Function
Euler's totient function phi(n) counts the integers from 1 to n that are coprime to n.
Essential for RSA encryption and number theory.
The Formula
Euler's totient function φ(n) (read "phi of n") counts how many integers from 1 to n are coprime to n — that is, share no common factor with n other than 1. Leonhard Euler introduced this function in 1763. It appears throughout number theory and is the basis for Euler's theorem and RSA public-key cryptography.
Special Cases
| Case | Formula | Reason |
|---|---|---|
| p is prime | φ(p) = p − 1 | All integers 1 to p−1 are coprime to a prime |
| p^k (prime power) | φ(p^k) = p^k − p^(k−1) | Only multiples of p are not coprime |
| n = pq (distinct primes) | φ(pq) = (p−1)(q−1) | Multiplicative property |
| φ(1) | 1 | By convention |
The totient function is multiplicative: if gcd(m, n) = 1, then φ(mn) = φ(m)φ(n).
Example 1 — Computing φ(12)
Find φ(12). The prime factorization of 12 = 2² × 3.
φ(12) = 12 × (1 − 1/2) × (1 − 1/3)
= 12 × 1/2 × 2/3
= 12 × 1/3 = 4
The 4 integers from 1 to 12 coprime to 12 are: {1, 5, 7, 11}
Example 2 — RSA Key Generation
RSA key generation with primes p = 61 and q = 53.
n = p × q = 61 × 53 = 3233
φ(n) = (p−1)(q−1) = 60 × 52 = 3120
Choose public exponent e = 17 (coprime to 3120)
Find private exponent d such that e × d ≡ 1 (mod φ(n))
d = 2753 (since 17 × 2753 = 46801 = 15 × 3120 + 1). Public key: (e=17, n=3233), private key: (d=2753, n=3233)
When to Use It
Use Euler's totient function when:
- RSA cryptography: The totient is used to generate RSA key pairs
- Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1 — the generalization of Fermat's little theorem
- Counting problems: How many fractions k/n in lowest terms exist for 1 ≤ k ≤ n?
- Primitive roots: An integer g is a primitive root mod n if g^φ(n) is the smallest power congruent to 1
- Necklace counting: Burnside's lemma uses the totient to count distinct necklace patterns