Euler's Generalization

Number Theory · Axiom Academy

Discover how Euler extended Fermat's theorem from primes to all numbers. Let's start by exploring Fermat's Little Theorem. Choose a prime number and a base to see the pattern Fermat discovered. Try different combinations. Notice that a p-1 ≡ 1 (mod p) always holds! ❌ Step 2: When Primes Aren't Available What if we need to work with composite numbers? Let's try using Fermat's formula with n = 12 (not prime). Try different bases. Fermat's formula doesn't work for composite numbers! Step 3: Euler's Counting Trick Euler asked: "How many numbers less than n are coprime to n?" Click numbers below to see which ones share no common factors with n = 12. Now let's use φ(n) as our exponent instead of n-1. Watch what happens! If p is prime and gcd(a, p) = 1: Works for all positive integers! When n is prime, φ(n) = n - 1, so Euler's theorem becomes Fermat's theorem. Euler generalized Fermat's discovery by using the totient function! • RSA Cryptography: Uses Euler's theorem with composite moduli • Modular Arithmetic: Simplifies large exponentiations • Number Theory: Foundation for modern algebraic structures

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