Euler's theorem

Statement

Let $n$ be a positive integer and let $a$ be an integer coprime to $n$. Then $a^{\varphi(n)} \equiv 1 \pmod n$, where $\varphi$ is Euler's totient function.

Remarks

When $n = p$ is prime, $\varphi(p) = p - 1$, and the result is Fermat's little theorem. A proof uses Lagrange's theorem: the group $(\mathbb{Z}/n\mathbb{Z})^\times$ has order $\varphi(n)$, by the number of invertible residues modulo n. The result lets us reduce exponents. If $\gcd(a, n) = 1$ and $k \equiv l \pmod{\varphi(n)}$, then $a^k \equiv a^l \pmod n$. For example, $\varphi(10) = 4$, so $7^{4} \equiv 1 \pmod{10}$, and the last digit of $7^{222}$ is the last digit of $7^2 = 49$, that is, $9$.

History

Euler proved the theorem in 1763.

Explanations

L1 human

Powers of $a$ modulo $n$ repeat in a cycle, and the cycle comes back to $1$. Euler's theorem gives one exponent that always brings $a$ back to $1$, namely $\varphi(n)$. For $n = 12$ and $a = 5$: $\varphi(12) = 4$ and $5^4 = 625 = 52 \cdot 12 + 1$.