Fermat's little theorem (statement): Worked examples

This page is the "throw everything at it" companion to Fermat's little theorem (statement). The parent gave you the statement; here we drill through every kind of situation the theorem can be dropped into, so that when an exam or a real computation hands you a strange-looking case, you have already seen its cousin.

Before we start, a one-line refresher of the only two facts we lean on. If $p$ is a prime (a whole number bigger than 1 whose only divisors are 1 and itself) and $a$ is coprime to $p$ (they share no factor bigger than 1, written $g cd (a, p) = 1$ ), then

$a^{p - 1} \equiv 1 (mod p)$

and for any integer $a$ at all,

$a^{p} \equiv a (mod p) .$

The notation $x \equiv y (mod p)$ just means " $x$ and $y$ leave the same remainder when divided by $p$ " — think of a clock with $p$ hours. If that clock idea is fuzzy, revisit Modular Arithmetic Basics first.

The scenario matrix

Every problem you can be handed with this theorem falls into one of these cells. The worked examples below are labelled with the cell they hit, and together they cover all of them.

Cell	What makes it that case	Covered by
A. Direct check	small $p$ , coprime $a$ — just verify	Example 1
B. Huge exponent	reduce exponent using $a^{p - 1} \equiv 1$	Example 2
C. $a > p$ (reduce base first)	base bigger than modulus	Example 3
D. $g cd (a, p) \neq = 1$ (degenerate)	$a$ is a multiple of $p$	Example 4
E. Negative base	$a < 0$	Example 5
F. Modular inverse	use $a^{- 1} \equiv a^{p - 2}$	Example 6
G. Non-prime modulus (trap)	$p$ composite — theorem fails	Example 7
H. Real-world word problem	RSA-flavoured decryption	Example 8
I. Exam twist	exponent as a tower / mixed forms	Example 9

The worked examples

Worked example Example 1 — Cell A: Direct check

Problem: Verify Fermat's Little Theorem for $p = 7$ , $a = 3$ .

Forecast: Before reading on, guess: what must $3^{6} mod 7$ equal? (If the theorem is real, it can only be one number.)

Step 1. Check the conditions: $7$ is prime, and $g cd (3, 7) = 1$ because 3 and 7 share no factor. Why this step? The theorem is a promise that only holds when both boxes are ticked — checking first stops us applying it illegally.

Step 2. Compute the power $a^{p - 1} = 3^{6} = 729$ . Why this step? The theorem talks about the $(p - 1)$ -th power specifically, and $p - 1 = 6$ .

Step 3. Divide by 7 and read the remainder: $729 = 104 \cdot 7 + 1$ . Why this step? " $\equiv 1 (mod 7)$ " literally means "remainder 1 after dividing by 7".

$3^{6} \equiv 1 (mod 7) ✓$

Verify: $104 \cdot 7 = 728$ , and $728 + 1 = 729$ . The remainder is exactly 1, as promised.

Worked example Example 2 — Cell B: Huge exponent

Problem: Find $2^{100} mod 13$ .

Forecast: $2^{100}$ has 31 digits. Guess whether the answer is a big number or a small one between 0 and 12.

Step 1. Conditions: $13$ is prime, $g cd (2, 13) = 1$ . So $2^{12} \equiv 1 (mod 13)$ . Why this step? $p - 1 = 12$ is the "reset point": every 12 factors of 2 collapse to 1.

Step 2. Split the exponent around 12: $100 = 12 \cdot 8 + 4$ . Why this step? We want to peel off as many full blocks of 12 as possible, because each block is worth 1.

Step 3. Rewrite: $2^{100} = (2^{12})^{8} \cdot 2^{4} \equiv 1^{8} \cdot 2^{4} (mod 13)$ . Why this step? $(2^{12})^{8}$ is $1$ raised to a power, which is just $1$ — the giant part vanishes.

Step 4. Compute the leftover: $2^{4} = 16 \equiv 3 (mod 13)$ (since $16 - 13 = 3$ ). Why this step? Only the "remainder exponent" 4 survives, and it is small enough to compute by hand.

$2^{100} \equiv 3 (mod 13)$

Verify: $2^{12} = 4096 = 315 \cdot 13 + 1$ , so indeed $2^{12} \equiv 1$ . And $16 = 13 + 3$ . Both checks pass.

Worked example Example 4 — Cell D: Degenerate,

$g cd (a, p) \neq = 1$ Problem: What is $3 5^{6} mod 7$ ? (Here $a = 35$ , which is a multiple of $7$ .)

Forecast: The classical form promises $a^{6} \equiv 1$ . Guess whether that promise holds here — remember the coprimality condition.

Step 1. Check coprimality: $g cd (35, 7) = 7 \neq = 1$ . The classical form does not apply. Why this step? Fermat's classical form silently assumes $p ∤ a$ . Skipping this check is the classic trap.

Step 2. Reduce the base: $35 = 5 \cdot 7 \equiv 0 (mod 7)$ . Why this step? 35 sits exactly on the 0 mark of the 7-clock.

Step 3. Then $3 5^{6} \equiv 0^{6} = 0 (mod 7)$ . Why this step? Zero times itself any number of times is still zero.

$3 5^{6} \equiv 0 (mod 7) (not 1!)$

Verify (via the alternative form, which does work for all $a$ ): $3 5^{7} \equiv 35 \equiv 0 (mod 7)$ , consistent with $35 \equiv 0$ . See Euler's Totient Function for the tool that repairs the coprime case for composite moduli.

Worked example Example 6 — Cell F: Modular inverse via FLT

Problem: Find the inverse of $3$ modulo $7$ , i.e. the number $x$ with $3 x \equiv 1 (mod 7)$ .

Forecast: Guess $x$ mentally: which of $1..6$ times 3 lands on 1 (mod 7)?

Step 1. Use the FLT inverse formula $a^{- 1} \equiv a^{p - 2} (mod p)$ , so here $3^{- 1} \equiv 3^{5} (mod 7)$ . Why this step? Because $a \cdot a^{p - 2} = a^{p - 1} \equiv 1$ , the power $a^{p - 2}$ is the inverse by definition. This turns "solve an equation" into "compute a power".

Step 2. Compute $3^{5} = 243$ . Why this step? We just need the value of that specific power.

Step 3. Reduce: $243 = 34 \cdot 7 + 5$ , so $3^{5} \equiv 5 (mod 7)$ . Why this step? The inverse must be one of $1..6$ ; the remainder gives it.

$3^{- 1} \equiv 5 (mod 7)$

Verify: $3 \cdot 5 = 15 = 2 \cdot 7 + 1 \equiv 1 (mod 7)$ . It undoes multiplication by 3, so it truly is the inverse. This trick underlies Modular Exponentiation Algorithms.

Worked example Example 7 — Cell G: The composite-modulus trap

Problem: A student writes " $5^{8} \equiv 1 (mod 9)$ by Fermat, since $9 - 1 = 8$ ." Is it right?

Forecast: $9$ is not prime. Guess whether the answer is really 1.

Step 1. Check primality: $9 = 3 \times 3$ , composite. FLT's guarantee simply does not apply. Why this step? The whole theorem hinges on $p$ prime; without it, there is no promise at all.

Step 2. Compute directly anyway: $5^{2} = 25 \equiv 7$ , $5^{4} \equiv 7^{2} = 49 \equiv 4$ , $5^{8} \equiv 4^{2} = 16 \equiv 7 (mod 9)$ . Why this step? Squaring step by step keeps numbers small and shows the true value.

$5^{8} \equiv 7 (mod 9) (not 1)$

Step 3. The correct exponent for a composite modulus comes from Euler's Totient Function: $ϕ (9) = 6$ , and indeed $5^{6} \equiv 1 (mod 9)$ . Why this step? Euler's theorem is the correct generalisation; the reset point is $ϕ (n)$ , not $n - 1$ .

Verify: $5^{6} = 15625 = 1736 \cdot 9 + 1 \equiv 1 (mod 9)$ . The magic reset is at 6, not 8 — see also Carmichael Numbers for composites that fake the prime behaviour.

Worked example Example 8 — Cell H: Real-world (mini-RSA decryption)

Problem: In a toy RSA Cryptosystem with prime $p = 11$ , a ciphertext value is $c = 8$ and the decryption exponent is $d = 7$ . Recover the message $m \equiv c^{d} (mod 11)$ and use FLT to keep the arithmetic tiny.

Forecast: The answer is a single digit between 0 and 10. Guess it will be small.

Step 1. $11$ prime, $g cd (8, 11) = 1$ , so $8^{10} \equiv 1 (mod 11)$ . The exponent $7$ is already below 10, so no reduction of the exponent is needed here. Why this step? FLT tells us the reset point is 10; since $7 < 10$ we compute directly, but we check first so we don't over-reduce.

Step 2. Compute by squaring: $8^{2} = 64 \equiv 9$ , $8^{4} \equiv 9^{2} = 81 \equiv 4$ , $8^{7} = 8^{4} \cdot 8^{2} \cdot 8 \equiv 4 \cdot 9 \cdot 8 (mod 11)$ . Why this step? $7 = 4 + 2 + 1$ , so we combine the pieces we already have — this is exactly fast exponentiation.

Step 3. $4 \cdot 9 = 36 \equiv 3$ , then $3 \cdot 8 = 24 \equiv 2 (mod 11)$ . Why this step? Reduce after each multiply to keep everything under 11.

$m \equiv 2 (mod 11)$

Verify: $8^{7} = 2097152 = 190650 \cdot 11 + 2 \equiv 2 (mod 11)$ . The recovered message is 2.

Worked example Example 9 — Cell I: Exam twist (a power tower)

Problem: Find $3^{(3^{5})} mod 7$ . That is, the exponent is itself $3^{5} = 243$ .

Forecast: The number is astronomically large. Guess: to tame the exponent, which modulus should we reduce the exponent by — $7$ or $6$ ?

Step 1. Conditions: $7$ prime, $g cd (3, 7) = 1$ , so $3^{6} \equiv 1 (mod 7)$ . The reset point for the exponent is $p - 1 = 6$ . Why this step? Because $3^{6} \equiv 1$ , only the exponent modulo 6 matters. Reducing the exponent by 6 (not by 7) is the key insight the twist tests.

Step 2. Reduce the tall exponent modulo 6: $3^{5} = 243$ , and $243 = 40 \cdot 6 + 3$ , so $243 \equiv 3 (mod 6)$ . Why this step? We only need the exponent's remainder after dividing by 6 to know how far past the reset we land.

Step 3. So $3^{243} \equiv 3^{3} (mod 7)$ , and $3^{3} = 27 = 3 \cdot 7 + 6 \equiv 6 (mod 7)$ . Why this step? The giant exponent 243 behaves exactly like the tiny exponent 3.

$3^{(3^{5})} \equiv 6 (mod 7)$

Verify: $243 mod 6 = 3$ and $3^{3} = 27 \equiv 6 (mod 7)$ . Reducing the exponent mod $p - 1$ is the whole trick — grounded in the Multiplicative Group Modulo Prime having order $p - 1$ .

Figure — Fermat's little theorem (statement)

The figure above shows the "reset clock" idea that every example above relies on: powers of $a$ march around the residues $1, 2, \dots, p - 1$ and land back on 1 exactly every $p - 1$ steps.

Recall Which cell is which?

Answer $2^{100} mod 13$ needs which trick? ::: Cell B — reduce the exponent mod $p - 1 = 12$ . Why does $3 5^{6} \equiv 0 (mod 7)$ instead of 1? ::: Cell D — $g cd (35, 7) = 7 \neq = 1$ , coprimality fails. For $5^{8} mod 9$ , why can't we use FLT? ::: Cell G — $9$ is composite; use $ϕ (9) = 6$ instead. To find $3^{- 1} mod 7$ , which power do we compute? ::: $3^{p - 2} = 3^{5} \equiv 5$ (Cell F). In $3^{(3^{5})} mod 7$ we reduce the exponent by which number? ::: By $p - 1 = 6$ , not by 7 (Cell I).

Connections

Fermat's little theorem (statement) — the parent statement this page drills.
Modular Arithmetic Basics — the clock arithmetic behind every reduction.
Euler's Totient Function — repairs Cells D and G (composite / non-coprime).
Multiplicative Group Modulo Prime — why the reset point is exactly $p - 1$ .
Modular Exponentiation Algorithms — the fast-squaring used in Examples 7–9.
RSA Cryptosystem — the real-world Cell H application.
Carmichael Numbers — composites that mimic the prime pattern.
Properties of Prime Numbers — why primality is non-negotiable.