Euler's theorem

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.