Euler's theorem

Euler's theorem states that if a and n are coprime positive integers, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function counting the integers up to n that are coprime to n. This result, proved by Leonhard Euler in 1763, is the generalization of Fermat's little theorem to composite moduli and the mathematical backbone of the RSA algorithm: the encryption and decryption exponents are chosen precisely so that their product is congruent to 1 modulo φ(n).

The theorem belongs to the deeper structure of modular arithmetic, where the multiplicative group of integers modulo n has order φ(n). Understanding why Euler's theorem works — why the group structure guarantees this periodicity — is understanding why RSA works, and why its security rests on the difficulty of computing φ(n) without knowing the factorization of n.