= Euler's theorem
{c}
{title2=$a^{\varphi(n)}\equiv1\pmod n$}
{wiki}
= Fermat-Euler theorem
{c}
{synonym}
For an <integer modulus> $n\geq2$ and an <integer> $a$ with <greatest common divisor> $\gcd(a,n)=1$, Euler's theorem, also called the <Fermat-Euler theorem>, states
$$
a^{\varphi(n)}\equiv1\pmod n.
$$
Here <Euler's totient function> $\varphi(n)$ counts the <units> in the <unit group> $U(n)=(\mathbb Z/n\mathbb Z)^\times$. These <congruence classes> have <modular multiplicative inverses>, equivalently their representatives are <coprime> to $n$. The guaranteed return to one permits <exponent reduction for units>.<Euler’s Theorem by Keith Conrad>[p. 1, Theorem 1.2 and equation (1.1): modulus at least two, invertible classes and totient]{ref}
For a <prime number> $p$, $\varphi(p)=p-1$, recovering <Fermat's little theorem> in the form $a^{p-1}\equiv1\pmod p$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a\pmod p$ for every <integer> $a$. For a <composite number> used as the <integer modulus>, a nonzero <congruence class> can be a <nonunit>.
Modulo twelve, the <units> have representatives $1,5,7,11$, so <Euler's totient function> gives $\varphi(12)=4$. <Multiplication> by five produces
$$
1\longmapsto5\longmapsto1,\qquad
7\longmapsto11\longmapsto7\pmod{12}.
$$
Thus this <permutation> has two <permutation cycles>, each of length two. In particular $5^2\equiv1\pmod{12}$, and the guaranteed return $5^4\equiv1$ follows. \b[The number of <units> need not be the length of one <permutation cycle>.] Modulo fifteen, <multiplication> by seven similarly gives the two <permutation cycles> $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight <units>. The powers of seven follow the <permutation cycle> containing one; the other <permutation cycle> shows that these powers do not visit every <unit>.
\Image[/euler-unit-residue-permutation-cycles.png]
{title=Two <unit> <permutations>: <multiplication> by five modulo twelve and by seven modulo fifteen}
{description=Every arrow multiplies by the indicated <unit> and reduces modulo the indicated <integer modulus>. The <permutation cycles> exhaust each <reduced residue system>. The <permutation cycle> containing one records the powers of the multiplier; its length is the multiplier's <multiplicative order>, which can be smaller than <Euler's totient function>.}
There is a stronger obstruction for a <nonunit> than just an occasional failed calculation. If a <positive integer> $d>1$ divides both $a$ and $n$, then $a^k\equiv0\pmod d$ for every $k\geq1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd(3,15)=3$ and $3^{\varphi(15)}=3^8\equiv6\pmod{15}$, rather than one. Such a base has no <multiplicative order> modulo that <integer modulus>.<Orders of Units in Modular Arithmetic by Keith Conrad>[p. 2, explanation following Example 1.8: a positive-exponent return to one forces coprimality]{ref}
Back to article page
