Fermat's and Euler's Theorems

Cryptography · Axiom Academy

LESSON Fermat's and Euler's Theorems The foundational theorems for RSA cryptography and modular exponentiation One of the most elegant results in number theory, discovered by Pierre de Fermat in 1640: This means that raising any number to the power p -1 and taking the remainder modulo p always gives 1 (as long as the number isn't divisible by p ). The proof relies on a clever observation about multiplication modulo a prime: Consider multiplying a by each non-zero element modulo p : These products give you all non-zero remainders modulo p in some order (just rearranged). Therefore: Both sides have the same product of 1, 2, ..., ( p -1). Dividing both sides by this product: This elegant argument shows why the pattern always holds for primes! To generalize Fermat's theorem to composite numbers, Euler introduced the totient function: φ(7) = 6 (all of 1, 2, 3, 4, 5, 6 are coprime to 7) φ(8) = 4 (only 1, 3, 5, 7 are coprime to 8) φ(15) = 8 (the numbers 1, 2, 4, 7, 8, 11, 13, 14 are coprime to 15) Euler generalized Fermat's Little Theorem to work with any modulus: Notice that when n = p (prime), we have φ( p ) = p -1, so Euler's Theorem reduces to Fermat's Little Theorem! The RSA cryptosystem relies on a beautiful application of Euler's Theorem: Choose two large primes p and q , compute n = pq Compute φ( n ) = ( p -1)( q -1) Choose encryption exponent e coprime to φ( n ) Find decryption exponent d such that ed ≡ 1 (mod φ( n )) Encrypting message m : c = m e (mod n )

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