Fermat's Little Theorem

Fermat's Little Theorem

If $p$ is a prime and $a$ is not divisible by $p$, then:

$a^{p-1} \equiv 1 \pmod{p}$

This means $a^{p-1}$ always has remainder 1 when divided by $p$. This is incredibly useful for computing large powers mod a prime.

Step-by-step: Find $2^{100} \mod 13$

Step 1 — Check conditions. $p = 13$ is prime, and $\gcd(2, 13) = 1$ (2 is not divisible by 13). ✓

Step 2 — Apply Fermat's Little Theorem. $2^{12} \equiv 1 \pmod{13}$ (since $p - 1 = 12$).

Step 3 — Express the exponent in terms of 12. $100 = 12 \times 8 + 4$, so:

$2^{100} = 2^{12 \times 8 + 4} = (2^{12})^8 \times 2^4$

Step 4 — Simplify using the theorem.

$(2^{12})^8 \times 2^4 \equiv 1^8 \times 2^4 \equiv 1 \times 16 \equiv 16 \pmod{13}$

Step 5 — Reduce $16 \mod 13$.

$16 = 13 + 3, \quad \text{so } 16 \equiv 3 \pmod{13}$

$\boxed{2^{100} \equiv 3 \pmod{13}}$

Verification: Computing $2^{12} = 4096$. $4096 / 13 = 315$ remainder $1$. ✓ So $2^{12} \equiv 1 \pmod{13}$.

The cyclic pattern of powers

$2^1 \equiv 2, \; 2^2 \equiv 4, \; 2^3 \equiv 8, \; 2^4 \equiv 3, \; 2^5 \equiv 6, \; 2^6 \equiv 12, \; 2^7 \equiv 11, \; 2^8 \equiv 9, \; 2^9 \equiv 5, \; 2^{10} \equiv 10, \; 2^{11} \equiv 7, \; 2^{12} \equiv 1 \pmod{13}$

The pattern repeats every 12 steps! This is what Fermat's theorem guarantees.

Why this matters

Without the theorem, computing $2^{100} \mod 13$ would require calculating a 31-digit number. With the theorem, we reduce it to $2^4 = 16 \equiv 3$. This shortcut is essential in cryptography — RSA encryption relies on modular exponentiation with very large primes.

Try it in the visualization

Enter base $a$ and prime $p$. The powers $a^1, a^2, \ldots, a^{p-1}$ are computed mod $p$, showing the cyclic pattern. The cycle always returns to 1 at $a^{p-1}$, confirming Fermat's theorem.