Fermat's Little Theorem in Puzzles

What is the remainder when $2^{100}$ is divided by 101? Computing $2^{100}$ directly gives a 31-digit number — not something to do by hand in an interview. But 101 is prime, and that single fact makes the problem almost trivial once you know Fermat's little theorem.

The core idea: a prime modulus forces powers to cycle back to 1

Fermat's little theorem states: if $p$ is a prime number and $a$ is any integer not divisible by $p$, then

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

In plain English: raise $a$ to the power one less than the prime, divide by the prime, and the remainder is always exactly 1 — no matter which valid $a$ or which prime $p$ you pick. This holds because the nonzero remainders $1, 2, \dots, p-1$ under multiplication modulo $p$ form a tightly structured group (every nonzero remainder has a multiplicative "partner" that undoes it), and a foundational fact about that structure — closely related to counting how repeated multiplication permutes the remainders — forces every element's $(p-1)$-th power back to 1.

Worked example 1: $2^{100} \bmod 101$

Since 101 is prime and $2$ isn't a multiple of 101, Fermat's little theorem gives $2^{100} \equiv 1 \pmod{101}$ directly — the exponent 100 is exactly $p - 1$ for $p=101$, so no further computation is needed. The remainder is 1.

Worked example 2: an exponent that isn't exactly $p-1$

What is $3^{206} \bmod 7$? Here $p=7$ is prime, so Fermat's little theorem says $3^6 \equiv 1 \pmod 7$. The exponent 206 isn't $6$, but you can use the theorem to reduce it: since $3^6 \equiv 1$, any multiple of 6 in the exponent also gives 1, so $3^{206} = 3^{6 \times 34 + 2} = (3^6)^{34} \times 3^2 \equiv 1^{34} \times 3^2 = 9 \pmod 7$. And $9 \bmod 7 = 2$. So $3^{206} \equiv 2 \pmod 7$. The technique generalizes: to compute $a^n \bmod p$ for prime $p$, first reduce the exponent $n$ modulo $p-1$ (using Fermat's little theorem to collapse full cycles of $p-1$ down to 1), then compute the much smaller resulting power directly.

What this means in practice

This is the number-theoretic engine behind RSA encryption and most public-key cryptography, where huge modular exponentiations need to be both computable and provably hard to reverse without the right key. In interviews, the pattern-recognition step — noticing that a modulus is prime and that the question is really asking for a modular power — is the real skill being tested, since the theorem itself is a one-line lookup once you spot it applies.