|
Euler's theorem (another Prime Pages' Glossary entries) |
|
|
Glossary:
Prime Pages:
Top 5000:
|
Euler's Theorem states that if
gcd(a,n) = 1, then
aphi(n) = 1 (mod n).
Here phi(n) (usually written
 )
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, phi(12)=4, so if gcd(a,12) = 1, then a4 = 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 Caldwell © 1999-2010 (all rights reserved)
|