Euler's Theorem

Number Theory · Axiom Academy

A fundamental result in modular arithmetic generalizing Fermat's Little Theorem where φ(n) is Euler's totient function, counting integers from 1 to n that are coprime to n. Example: Let's see this with n = 10 and a = 3. First, φ(10) = 4 (the numbers 1, 3, 7, 9 are coprime to 10). According to Euler's Theorem: 3 4 ≡ 1 (mod 10) Let's verify: 3 4 = 81 = 8(10) + 1 ≡ 1 (mod 10) ✓ A reduced residue system modulo n is a set of φ(n) integers that are coprime to n, with exactly one from each coprime residue class. Key Insight: If r₁, r₂, ..., r φ(n) is an RRS modulo n, and gcd(a, n) = 1, then: ar₁, ar₂, ..., ar φ(n) is also an RRS modulo n RRS = 1, 3, 7, 9 (the 4 numbers coprime to 10) 3·1 = 3, 3·3 = 9, 3·7 = 21 ≡ 1, 3·9 = 27 ≡ 7 (mod 10) New set: 3, 9, 1, 7 = 1, 3, 7, 9 - same RRS, just permuted! 3. Proof Using Reduced Residue Systems 4. Relationship to Fermat's Little Theorem If p is prime and gcd(a, p) = 1, then: Euler's Theorem generalizes Fermat's Little Theorem! When n = p (a prime), we have: φ(p) = p - 1 (all numbers 1, 2, ..., p-1 are coprime to p) Substituting into Euler's Theorem: This is exactly Fermat's Little Theorem!

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