How can you shrink a huge exponent before computing $a^y \bmod n$, and what condition must hold? Compute $14^{51} \bmod 9$.
If $\gcd(a, n) = 1$, reduce the exponent mod $\varphi(n)$ and the base mod $n$. Here $14^{51} \equiv 5^{3} \equiv 8 \pmod 9$.
The general rule (Euler, with Fermat as the prime case): for $\gcd(a, n) = 1$, $$a^y \equiv a^z \pmod n \quad\text{whenever}\quad y \equiv z \pmod{\varphi(n)}$$ and, since the base can be reduced too, $$a^y \equiv b^z \pmod n \quad\text{whenever}\quad y \equiv z \pmod{\varphi(n)} \text{ and } a \equiv b \pmod n$$
For a prime $p$ this reads $y \equiv z \pmod{p-1}$, because $\varphi(p) = p - 1$.
Why it works: $a^{\varphi(n)} \equiv 1$, so every full block of $\varphi(n)$ in the exponent multiplies by 1 and can be dropped.
Worked example, $14^{51} \bmod 9$:
- $\gcd(14, 9) = 1$, so the rule applies; $\varphi(9) = 6$.
- Exponent: $51 \bmod 6 = 3$.
- Base: $14 \bmod 9 = 5$.
- $5^3 = 125 = 13 \cdot 9 + 8$, so the result is 8.
More examples:
- $10^{15} \bmod 7$: $15 \bmod 6 = 3$, so $10^{3} \equiv 3^{3} = 27 \equiv 6$.
- $22^{32} \bmod 27$: $\varphi(27) = 18$, $32 \bmod 18 = 14$, so $22^{32} \equiv 22^{14} \equiv 7$.
Gotcha: the exponent is reduced mod $\varphi(n)$, never mod $n$. And the rule needs $\gcd(a, n) = 1$: for $a = 14$, $p = 7$ we get $14^6 \equiv 0 \not\equiv 1 \pmod 7$.