Number TheoryDifficulty 35-85171 tagged problems

Fermat's Little Theorem

Fermat's Little Theorem is the habit of reducing powers modulo primes using $a^{p-1}\equiv 1$ when $a$ is not divisible by $p$. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$a^{p-1} \equiv 1 \pmod{p} \quad \text{for prime } p \text{ and } \gcd(a, p) = 1$$

Raising any integer not divisible by a prime $p$ to the power $p-1$ always gives $1$ modulo $p$, which collapses huge exponents.

Why It Works

1
Consider the residues $a, 2a, 3a, \dots, (p-1)a$ modulo $p$.
2
Since $\gcd(a,p)=1$, multiplication by $a$ is a bijection on the nonzero residues, so these are just $1, 2, \dots, p-1$ rearranged.
3
Multiplying both lists: $a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}$.
4
As $(p-1)!$ is coprime to $p$, cancel it to get $a^{p-1} \equiv 1 \pmod p$.

Worked Examples

Example 1

Compute $3^{100} \bmod 7$.

1
Here $p = 7$ is prime and $\gcd(3,7) = 1$, so $3^{6} \equiv 1 \pmod 7$.
2
Reduce the exponent mod $6$: $100 = 6 \cdot 16 + 4$, so $3^{100} \equiv 3^{4} \pmod 7$.
3
Compute $3^4 = 81$.
4
Reduce: $81 = 7 \cdot 11 + 4$, so $3^{100} \equiv 4 \pmod 7$.

Answer:

$4$

Warm-up

Compute $2^{50} \bmod 13$.

1
$13$ is prime and $\gcd(2, 13) = 1$, so Fermat gives $2^{12} \equiv 1 \pmod{13}$.
2
Reduce the exponent mod $12$: $50 = 12 \cdot 4 + 2$, so $2^{50} \equiv 2^2 \pmod{13}$.
3
Compute $2^2 = 4$.
4
Hence $2^{50} \equiv 4 \pmod{13}$.

Answer:

$4$

Contest level

Find the remainder when $7^{7^{7}}$ (a power tower, $7^{(7^7)}$) is divided by $13$.

1
By Fermat, $7^{12} \equiv 1 \pmod{13}$, so we need the exponent $7^7$ modulo $12$.
2
Compute $7^7 \bmod 12$: $7^2 = 49 \equiv 1 \pmod{12}$, so $7^7 = 7^{2\cdot3}\cdot 7 \equiv 1^3 \cdot 7 = 7 \pmod{12}$.
3
Therefore $7^{7^7} \equiv 7^{7} \pmod{13}$.
4
Compute $7^7 \bmod 13$: $7^2 = 49 \equiv 10$, $7^3 \equiv 70 \equiv 5$, $7^6 \equiv 5^2 = 25 \equiv 12 \equiv -1$, so $7^7 \equiv -7 \equiv 6 \pmod{13}$.

Answer:

$6$

Olympiad / Challenge

Prove that for every prime $p$, the number $p$ divides $\binom{2p}{p} - 2$.

1
By Fermat's little theorem in the form $a^p \equiv a \pmod p$ for all integers $a$, the binomial $(1 + x)^p \equiv 1 + x^p \pmod p$ as polynomials with integer coefficients (the freshman's dream, since $p \mid \binom{p}{k}$ for $0 < k < p$).
2
Then $(1 + x)^{2p} = \left((1+x)^p\right)^2 \equiv (1 + x^p)^2 = 1 + 2x^p + x^{2p} \pmod p$.
3
Compare the coefficient of $x^p$ on both sides: on the left it is $\binom{2p}{p}$, on the right it is $2$.
4
Therefore $\binom{2p}{p} \equiv 2 \pmod p$, i.e. $p \mid \binom{2p}{p} - 2$.

Answer:

$p \mid \binom{2p}{p} - 2$ for every prime $p$.

Going Deeper

Generalization: Fermat is the prime case of Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod n$ for $\gcd(a,n) = 1$ (with $\varphi(p) = p-1$). The cleaner sibling $a^p \equiv a \pmod p$ holds for ALL integers $a$, including multiples of $p$, and generalizes to $a^{p^k} \equiv a^{p^{k-1}} \pmod{p^k}$.
Where it appears: collapsing enormous exponents in $a^N \bmod p$, power-tower problems (reduce the tower from the top using the exponent's modulus), primality testing (Fermat / Miller–Rabin), and polynomial-coefficient arguments via $(1+x)^p \equiv 1 + x^p$.
Pitfall: Fermat requires $\gcd(a, p) = 1$ for the $a^{p-1} \equiv 1$ form — if $p \mid a$ then $a^{p-1} \equiv 0$, not $1$. When reducing the exponent of $a^E \bmod p$, reduce $E$ modulo $p - 1$ (or the order of $a$), NOT modulo $p$; and the converse fails — $a^{n-1}\equiv 1 \pmod n$ does not prove $n$ prime (Carmichael numbers like $561$ fool it).

Spot the Signal

Look for problems where the key step is reducing powers modulo primes using $a^{p-1}\equiv 1$ when $a$ is not divisible by $p$.
You can describe the hard part as reducing powers modulo primes using $a^{p-1}\equiv 1$ when $a$ is not divisible by $p$, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for fermat's little theorem, then rewrite the givens around it.
Name the relation that makes Fermat's Little Theorem legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Fermat's Little Theorem just because the surface looks familiar; verify the required condition first.
Applying Fermat's Little Theorem because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let fermat's little theorem reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is reducing powers modulo primes using $a^{p-1}\equiv 1$ when $a$ is not divisible by $p$.