Euler's Totient Function

Cryptography · Axiom Academy

LESSON Euler's Totient Function Understanding φ(n) and its crucial role in RSA cryptography 1. Definition and Basic Examples For any positive integer n, Euler's totient function φ(n) counts the integers from 1 to n that are relatively prime to n (i.e., gcd(k, n) = 1). Let's visualize this with n = 8. We check each number from 1 to 8: The numbers 1, 3, 5, and 7 are all relatively prime to 8, so φ(8) = 4. 2. The Totient Function for Prime Numbers When n is prime , every number from 1 to n-1 is relatively prime to n (since a prime has no divisors except 1 and itself). Let's visualize this with p = 7: φ(2) = 1 (only 1 is coprime to 2) φ(5) = 4 (numbers 1, 2, 3, 4 are all coprime to 5) φ(11) = 10 (numbers 1 through 10 are all coprime to 11) 3. The Totient Function for Prime Powers For prime powers p k , we can derive a formula by counting which numbers share a factor with p k . A number is NOT relatively prime to p k if and only if it's a multiple of p. There are p k-1 such multiples (p, 2p, 3p, ..., p k-1 ·p). φ(4) = φ(2²) = 2²⁻¹(2-1) = 2·1 = 2 φ(27) = φ(3³) = 3³⁻¹(3-1) = 9·2 = 18 φ(125) = φ(5³) = 5³⁻¹(5-1) = 25·4 = 100 4. The Multiplicative Property The totient function has a powerful property: it's multiplicative for coprime numbers. This follows from the Chinese Remainder Theorem. When m and n are coprime, the integers relatively prime to mn correspond exactly to pairs of integers relatively prime to m and n separately. Let's see this with m = 3 and n = 5:

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