Euler's theorem
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)

Euler's Theorem states that if gcd(a,n) = 1, then aphi(n) = 1 (mod n). Here phi(n) (usually written (using the Greek letter phi)) 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 K. Caldwell © 1999-2020 (all rights reserved)