Euler's Totient Function

Number Theory · Axiom Academy

LESSON Euler's Totient Function Discovering the fundamental counting function in number theory 1. Definition and Basic Examples In other words, φ(n) counts how many numbers from 1 to n share no common factors with n (except 1). φ(1) = 1 : Only 1 is coprime to itself φ(6) = 2 : Numbers 1 and 5 are coprime to 6 φ(8) = 4 : Numbers 1, 3, 5, 7 are coprime to 8 2. The Totient Function for Primes When n is a prime number p, every number from 1 to p-1 is coprime to p, since p has no divisors except 1 and itself. φ(7) = 6 : Numbers 1, 2, 3, 4, 5, 6 are all coprime to 7 φ(13) = 12 : Numbers 1, 2, 3, ..., 12 are all coprime to 13 φ(101) = 100 : All numbers from 1 to 100 are coprime to 101 For prime powers p k , we can derive a formula by counting which numbers are NOT coprime to p k . A number is coprime to p k if and only if it's not divisible by p. Among 1, 2, 3, ..., p k , exactly p k-1 numbers are multiples of p These are: p, 2p, 3p, ..., p k-1 · p = p k Therefore: φ(p k ) = p k - p k-1 = p k (1 - 1/p) Let's apply the prime power formula to concrete examples and verify our results. φ(9) = φ(3²) : Using p=3, k=2: φ(9) = 3²(1 - 1/3) = 9 · (2/3) = 6 Coprime numbers: 1, 2, 4, 5, 7, 8 φ(25) = φ(5²) : Using p=5, k=2: φ(25) = 25(1 - 1/5) = 25 · (4/5) = 20 Coprime numbers: all except 5, 10, 15, 20, 25 φ(16) = φ(2⁴) : Using p=2, k=4: φ(16) = 16(1 - 1/2) = 8 Coprime numbers: 1, 3, 5, 7, 9, 11, 13, 15 (all odd numbers)

This is the written version of the interactive lesson above. See the full Number Theory course.