Input
Fermat's Little Theorem
For any prime p and integer a not divisible by p:
a^(p-1) ≡ 1 (mod p)
Example: If p = 7 and a = 3:
3^6 mod 7 = 729 mod 7 = 1
Critical for RSA encryption and primality testing algorithms.
Euler's Theorem
If gcd(a, n) = 1, then:
a^φ(n) ≡ 1 (mod n)
Example: If n = 14 (φ(14) = 6) and a = 3:
3^6 mod 14 = 729 mod 14 = 1
Generalizes Fermat's theorem. Foundation for RSA private key calculation.
Connection to RSA Cryptography
RSA encryption relies heavily on these theorems:
Key Generation
Choose large primes p, q and compute n = p×q. Then φ(n) = (p-1)(q-1).
Encryption/Decryption
Public key (e, n), private key (d, n). Works because m^(ed) ≡ m (mod n).
Security
Security depends on difficulty of factoring n into p and q.