Fermat and Euler Summary

Number Theory · Axiom Academy

Let's review the fundamental theorems connecting exponents, modular arithmetic, and the structure of integers. Statement: If p is prime and gcd( a, p ) = 1, then a p -1 ≡ 1 (mod p ) Alternative Form: For any integer a and prime p : a p ≡ a (mod p ) Key Application: Efficiently computing large powers modulo primes, foundational for RSA cryptography Why It Matters: First major result connecting exponents with modular arithmetic Definition: φ( n ) counts integers from 1 to n that are relatively prime to n For Primes: φ( p ) = p - 1 when p is prime For Prime Powers: φ( p k ) = p k - p k -1 = p k -1 ( p - 1) Multiplicative Property: If gcd( m, n ) = 1, then φ( mn ) = φ( m )φ( n ) Example Recap: Computing 7 222 (mod 10) Step 1 - Verify Conditions: Check gcd(7, 10) = 1, so Euler's Theorem applies Step 2 - Calculate φ(n): φ(10) = φ(2)φ(5) = 1 × 4 = 4 Step 3 - Apply Euler's Theorem: Since 7 4 ≡ 1 (mod 10), reduce the exponent: 222 = 4(55) + 2 Step 4 - Compute: 7 222 = (7 4 ) 55 · 7 2 ≡ 1 55 · 49 ≡ 9 (mod 10) Definition: The order of a modulo n is the smallest positive integer k such that a k ≡ 1 (mod n ) Notation: Written as ord n ( a ) or o( a ) Key Property: The order always divides φ( n ) Powers Pattern: a m ≡ 1 (mod n ) if and only if ord( a ) divides m Definition: g is a primitive root modulo n if ord n ( g ) = φ( n ) Powers Generate Group: The powers g 1 , g 2 , ..., g φ( n ) produce all units mod n

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