# 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*^{4} ≡ 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.

Printed from the PrimePages <t5k.org> © Reginald McLean.