Euler's Theorem

Fermat's Little Theorem works only for prime moduli: aᵖ⁻¹ ≡ 1 (mod p). But Euler saw that the same idea holds for ANY modulus n, as long as a and n are coprime — just replace p − 1 with φ(n). This one generalization is why RSA can decrypt messages: it guarantees that after encrypting and then decrypting, you always land back on the original.