Euler's Totient Function φ(n)
What you'll learn: You'll understand how to count how many numbers less than or equal to n share no common factors with n.
The Core Idea
Euler's totient function, denoted φ(n) (read "phi of n"), counts the number of integers between 1 and n (inclusive) that are relatively prime to n — meaning they share no divisors with n except 1.
Think of it as a "compatibility counter": if you're working modulo n, φ(n) tells you how many numbers from 1 to n have modular inverses (the ones that are coprime to n).
Computing φ(n) by Inspection
For small n, you can list candidates and check:
Example 1: φ(8)
- Integers from 1 to 8: {1, 2, 3, 4, 5, 6, 7, 8}
- Which are coprime to 8? Check gcd(k, 8) = 1
- gcd(1,8)=1 ✓, gcd(2,8)=2 ✗, gcd(3,8)=1 ✓, gcd(4,8)=4 ✗
- gcd(5,8)=1 ✓, gcd(6,8)=2 ✗, gcd(7,8)=1 ✓, gcd(8,8)=8 ✗
- Count: {1, 3, 5, 7} → φ(8) = 4
Example 2: φ(9)
- Coprime to 9: {1, 2, 4, 5, 7, 8} (skip multiples of 3)
- φ(9) = 6
Example 3: φ(7)
- Since 7 is prime, all numbers 1 through 6 are coprime to 7
- φ(7) = 6
Pattern for primes: If p is prime, then φ(p) = p − 1, because every smaller positive integer is coprime to a prime.
Key Takeaway: φ(n) counts integers from 1 to n that are relatively prime to n; for any prime p, φ(p) = p − 1.