Euler's theorem

Euler's Theorem states that if gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n). Here φ(n) is Euler's totient function: the number of integers in {1, 2, . . ., n-1} which are relatively prime to n. When n is a prime, this theorem is just Fermat's little theorem.

For example, φ(12)=4, so if gcd(a,12) = 1, then a⁴ ≡ 1 (mod 12).

The set of residue classes {d mod n | gcd(d,n)=1} modulo n form a multiplicative group, so Euler's theorem is a special case of Lagrange's theorem: the order of an element divides the order of a group.