Repeated squaring makes huge powers cheap. For a prime modulus, a theorem from 1640 makes many of them free: the powers of $a$ mod $p$ come back to 1 after at most $p - 1$ steps, so a huge exponent can be shrunk before you start.
Fermat's little theorem. If $p$ is prime and $p \nmid a$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ Multiplying by $a$ gives a form that holds for every integer $a$: $a^{p} \equiv a \pmod{p}$.
Why it works
A second proof of the form $a^{p} \equiv a$ uses the binomial theorem. For $0 < k < p$, the coefficient $\binom{p}{k} = \frac{p!}{k!\,(p-k)!}$ has the prime $p$ upstairs and not downstairs, so $p \mid \binom{p}{k}$. Hence $(a + 1)^{p} \equiv a^{p} + 1 \pmod{p}$, and starting from $0^{p} = 0$ and adding 1 at a time gives $a^{p} \equiv a$ for every $a \ge 0$. Fermat stated the theorem in 1640 without proof; Euler published the first proof in 1736.
The payoff: reduce exponents mod $p - 1$. If $e = (p-1)q + r$, then $a^{e} = (a^{p-1})^{q} a^{r} \equiv a^{r} \pmod{p}$.
Worked example: A huge exponent
- $7$ is prime and $7 \nmid 3$, so $3^{6} \equiv 1 \pmod{7}$.
- $100 = 6 \cdot 16 + 4$, so $3^{100} \equiv 3^{4} = 81$.
- $81 = 7 \cdot 11 + 4$.
Answer: $3^{100} \equiv 4 \pmod{7}$.
Worked example: Another prime
- $2^{12} \equiv 1 \pmod{13}$. $1000 = 12 \cdot 83 + 4$.
- $2^{1000} \equiv 2^{4} = 16 \equiv 3 \pmod{13}$.
Answer: $3$.
Worked example: Inverses for free
- $3 \cdot 3^{5} = 3^{6} \equiv 1$, so $3^{-1} \equiv 3^{5} \pmod{7}$. In general $a^{-1} \equiv a^{p-2} \pmod{p}$.
- $3^{5} = 243 = 7 \cdot 34 + 5$, so $3^{-1} \equiv 5$. Check: $3 \cdot 5 = 15 \equiv 1$.
Answer: $5$.
Common mistake
Key idea