You open a problem. It reads: "Find the remainder when 3^{1000} is divided by 7." Your first instinct might be panic — 3^{1000} has over four hundred digits. Your calculator will not help. Your second instinct might be cleverness — look for a cycle of powers by hand. That works, but it is slow. There is a third instinct, and it is the one a trained eye reaches for immediately: the modulus is a prime, so Fermat's little theorem applies, and the exponent collapses.

This article is about the recognition signal. Not the proof, not the full theorem — you can read the demo article for that. Here the goal is narrower: to install a reflex. When you see "huge exponent, prime modulus," your pencil should already be writing p - 1 at the top of the page before you have finished reading the question.

The signal in two parts

Fermat's little theorem says: for a prime p and any integer a with \gcd(a, p) = 1,

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

The consequence that matters for computation is this: when you compute a^N \bmod p, the exponent N can be reduced modulo p - 1. Every multiple of p - 1 in the exponent is invisible — it just contributes a factor of 1 and vanishes. So

a^N \equiv a^{N \bmod (p-1)} \pmod p.

That is the collapse. A four-digit exponent becomes a single-digit exponent. A hundred-digit exponent becomes a one- or two-digit exponent. The problem that looked impossible becomes one line of arithmetic.

To spot when this tool applies, you need exactly two recognitions:

  1. The exponent is large. "Large" is relative — anything bigger than p - 1 counts, but in exam problems you typically see exponents in the hundreds, thousands, or tens of thousands. If the exponent is 4 and the modulus is 7, you do not need Fermat; you just compute a^4. Fermat earns its keep when the exponent would otherwise be unreachable.
  2. The modulus is prime. 7. 11. 13. 17. 1{,}000{,}003. If you see \bmod 6 or \bmod 15 or \bmod 100, Fermat does not apply directly — you need its generalisation, Euler's theorem, which I discuss at the end.

When both conditions hold, the signal fires: reduce the exponent \bmod\ (p - 1) and compute the tiny remaining power.

The flowchart

Fermat recognition flowchart A flowchart with four decision boxes leading to the action reduce exponent modulo p minus 1. Problem of the form a^N mod n Is N much larger than n? (say, N > 20) yes Is n prime? (call it p) yes Is gcd(a, p) = 1? (a not a multiple of p) yes Apply Fermat: replace N with N mod (p − 1) then compute the small power by hand
Three yes-answers and the collapse is yours. If any answer is no, the signal does not fire — you fall back to finding a cycle by hand, or to Euler's theorem for composite moduli.

Worked example: 3^{1000} \bmod 7

The signal fires immediately. Exponent 1000 is huge. Modulus 7 is prime. And \gcd(3, 7) = 1. So Fermat applies: 3^6 \equiv 1 \pmod 7.

Step 1 — reduce the exponent mod p - 1 = 6.

1000 = 6 \times 166 + 4, so 1000 \equiv 4 \pmod 6.

Step 2 — replace 3^{1000} with 3^4.

3^{1000} \equiv 3^4 \pmod 7.

Why this is valid: 3^{1000} = (3^6)^{166} \cdot 3^4 \equiv 1^{166} \cdot 3^4 = 3^4 \pmod 7. The 166 copies of 3^6 each collapse to 1 and drop out.

Step 3 — compute 3^4 \bmod 7.

3^2 = 9 \equiv 2 \pmod 7, so 3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod 7.

3^{1000} \equiv 4 \pmod 7.

Four lines. No calculator. A number that would have taken hours to write out by long multiplication, reduced to a single digit in the time it takes to sharpen a pencil.

Worked example: 2^{2024} \bmod 13

The signal fires again. 2024 is large. 13 is prime. \gcd(2, 13) = 1. So 2^{12} \equiv 1 \pmod{13}, and the exponent reduces mod 12.

Step 1 — reduce 2024 \bmod 12.

2024 = 12 \times 168 + 8, so 2024 \equiv 8 \pmod{12}.

Step 2 — replace 2^{2024} with 2^8.

2^{2024} \equiv 2^8 \pmod{13}.

Step 3 — compute 2^8 \bmod 13.

2^4 = 16 = 13 + 3 \equiv 3 \pmod{13}. So 2^8 = (2^4)^2 \equiv 3^2 = 9 \pmod{13}.

2^{2024} \equiv 9 \pmod{13}.

Notice how you never wrote 2^{2024} explicitly. You never touched the 609-digit number it represents. You jumped straight from the reduction to an eighth power, and from there to a single digit. That is the signature move of a Fermat problem.

The edge case: \gcd(a, p) \neq 1

Fermat requires a to be coprime to p. For a prime p, the only way that fails is if a is a multiple of p. If the question asks for 14^{1000} \bmod 7, you do not apply Fermat. You notice that 14 \equiv 0 \pmod 7, so 14^{1000} \equiv 0^{1000} = 0 \pmod 7. The answer is immediate and the theorem is not needed.

This edge case is rare in exam problems — usually the base is deliberately chosen coprime to the modulus. But a quick check of \gcd(a, p) costs nothing and saves you from applying the theorem where it does not hold.

When the modulus is composite: Euler's theorem

If the problem reads 7^{500} \bmod 10, the modulus is not prime. Fermat does not apply directly. But it has a generalisation — Euler's theorem — that handles composite moduli. Euler's theorem says: for any n and any a with \gcd(a, n) = 1,

a^{\phi(n)} \equiv 1 \pmod n,

where \phi(n) is Euler's totient function, counting integers from 1 to n that are coprime to n. For a prime p, \phi(p) = p - 1, and Euler's theorem reduces to Fermat's. For n = 10, \phi(10) = 4 (the coprimes are 1, 3, 7, 9), so 7^{500} \equiv 7^{500 \bmod 4} = 7^0 = 1 \pmod{10}.

The recognition signal widens: huge exponent, any modulus, base coprime to modulus — reduce the exponent mod \phi(n). Fermat is the cleanest, most common special case (prime modulus), but Euler covers the rest.

The reflex

Reading comprehension first. Whenever a problem asks for a remainder and involves an exponentiation, the first two things you look at are the exponent and the modulus. If the exponent is \geq 20 and the modulus is a prime p, your hand should already be writing "reduce exponent mod p - 1" before your brain has caught up. That reflex is what separates a ten-second answer from a ten-minute one.

Related: Modular Arithmetic · Fermat's Little Theorem Demo · Compute 2^100 mod 7 by Hand · Try Small Cases First · gcd = 1 Signals Bézout and Inverses