
Glossary: Prime Pages: Top 5000: 
Euler's Theorem states that if
gcd(a,n) = 1, then
a^{phi(n)} = 1 (mod n).
Here phi(n) (usually written
)
is Euler's totient function: the number of integers in
{1, 2, . . ., n1} which are relatively prime
to n. When n is a prime, this theorem
is just Fermat's little theorem.
For example, phi(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.
Chris K. Caldwell © 19992018 (all rights reserved)
