Fermat's little theorem (statement): Exercises

Everything rests on one line, so let us pin it down before we lean on it.

Figure — Fermat's little theorem (statement)

The figure above is our mental picture for the whole page: a clock with $p$ hours. Multiplying by $a$ just reshuffles the hour-marks $1, 2, \dots, p - 1$ , and after $p - 1$ steps of a certain journey you always return to $1$ . Keep it in mind.

Level 1 — Recognition

Here you only decide whether the theorem applies and read off the trivial consequence. No heavy arithmetic.

Recall Solution 1.1

The classical form needs both " $p$ prime" and " $g cd (a, p) = 1$ ".

(a) $p = 7$ is prime and $g cd (4, 7) = 1$ → applies. So $4^{6} \equiv 1 (mod 7)$ .
(b) $p = 9 = 3 \times 3$ is not prime → does not apply. FLT says nothing here (you would need Euler's theorem).
(c) $p = 5$ is prime but $g cd (10, 5) = 5 \neq = 1$ → does not apply. Here $10 \equiv 0$ , so $1 0^{4} \equiv 0 (mod 5)$ .
(d) $p = 13$ prime, $g cd (1, 13) = 1$ → applies, and trivially $1^{12} = 1 \equiv 1 (mod 13)$ .

Recall Solution 1.2

Both cases: $p$ prime, $g cd (a, p) = 1$ (since $6 < 11$ and $12 < 13$ are nonzero and $p$ is prime, neither shares a factor with $p$ ).

(a) $6^{10} \equiv 1 (mod 11)$ .
(b) $1 2^{12} \equiv 1 (mod 13)$ . The whole point of L1: once the two conditions pass, the answer to $a^{p - 1} mod p$ is always $1$ — you never actually multiply.

Level 2 — Application

Now you actually compute, but the exponent is close to $p - 1$ so the theorem does most of the work.

Recall Solution 2.1

$p = 11$ prime, $g cd (2, 11) = 1$ , and the exponent is exactly $p - 1 = 10$ . So directly by Form 1: $2^{10} \equiv 1 (mod 11) .$ (Sanity check: $2^{10} = 1024 = 93 \cdot 11 + 1$ . ✓)

Recall Solution 2.2

$p = 13$ prime, $g cd (5, 13) = 1$ .

$5^{12} \equiv 1 (mod 13)$ by Form 1 (exponent $= p - 1$ ).
$5^{13} = 5^{12} \cdot 5 \equiv 1 \cdot 5 = 5 (mod 13)$ . This is Form 2 in action: $a^{p} \equiv a$ . Answers: $5^{12} \equiv 1$ , $5^{13} \equiv 5 (mod 13)$ .

Recall Solution 2.3

$p = 7$ prime, $g cd (3, 7) = 1$ , exponent $= p - 1 = 6$ , so $3^{6} \equiv 1 (mod 7)$ . Verify: $3^{6} = 729 = 104 \cdot 7 + 1$ , so $729 \equiv 1 (mod 7)$ . ✓ Answer: $1$ .

Level 3 — Analysis

The exponent is now large and not a clean multiple of $p - 1$ . You must reduce it first.

Recall Solution 3.1

$p = 13$ prime, $g cd (7, 13) = 1$ , so $7^{12} \equiv 1 (mod 13)$ . We want to write $100$ using multiples of $12$ : $100 = 12 \cdot 8 + 4 (since 12 \cdot 8 = 96, 100 - 96 = 4) .$ Then $7^{100} = (7^{12})^{8} \cdot 7^{4} \equiv 1^{8} \cdot 7^{4} = 7^{4} (mod 13) .$ Compute $7^{2} = 49 \equiv 49 - 3 \cdot 13 = 10 (mod 13)$ , so $7^{4} = (7^{2})^{2} \equiv 1 0^{2} = 100 \equiv 100 - 7 \cdot 13 = 9 (mod 13)$ . Answer: $7^{100} \equiv 9 (mod 13)$ .

Recall Solution 3.2

$p = 17$ prime, so $2^{16} \equiv 1 (mod 17)$ . Reduce the exponent modulo $16$ : $1000 = 16 \cdot 62 + 8 (16 \cdot 62 = 992, 1000 - 992 = 8) .$ Hence $2^{1000} \equiv 2^{8} (mod 17)$ . Now $2^{8} = 256 = 15 \cdot 17 + 1 = 255 + 1$ , so $256 \equiv 1 (mod 17)$ . Answer: $2^{1000} \equiv 1 (mod 17)$ . (This "extra $1$ " is fine — it just means $2$ has a smaller cycle, order $8$ , dividing $16$ .)

Recall Solution 3.3

Careful: $g cd (6, 3) = 3 \neq = 1$ , so Form 1 does not apply. But $6 \equiv 0 (mod 3)$ , so $6^{50} \equiv 0^{50} = 0 (mod 3) .$ Every power of a multiple of $p$ stays $\equiv 0$ . Form 2 also confirms consistency: $6^{3} \equiv 6 \equiv 0$ . Answer: $0$ .

Level 4 — Synthesis

Combine FLT with modular inverses and multi-step arguments.

Recall Solution 4.1

Since $3 \cdot 3^{p - 2} = 3^{p - 1} \equiv 1$ , the inverse is $3^{p - 2} = 3^{9} (mod 11)$ . $3^{2} = 9$ , $3^{4} = 81 \equiv 4$ , $3^{8} = (3^{4})^{2} \equiv 4^{2} = 16 \equiv 5$ . Then $3^{9} = 3^{8} \cdot 3 \equiv 5 \cdot 3 = 15 \equiv 4 (mod 11)$ . Check: $3 \cdot 4 = 12 \equiv 1 (mod 11)$ . ✓ Answer: $3^{- 1} \equiv 4 (mod 11)$ .

Recall Solution 4.2

Proof. $p = 7$ is prime. Two cases:

If $g cd (a, 7) = 1$ : Form 1 gives $a^{6} \equiv 1$ , so $a^{7} = a \cdot a^{6} \equiv a \cdot 1 = a$ .
If $7 ∣ a$ : then $a \equiv 0$ , and $a^{7} \equiv 0 \equiv a$ . Both cases give $a^{7} \equiv a (mod 7)$ . This covers all integers. $■$ Computation. $10 \equiv 3 (mod 7)$ , so $1 0^{7} \equiv 3^{7} \equiv 3 (mod 7)$ (by the identity just proved). Answer: $1 0^{7} \equiv 3 (mod 7)$ .

Recall Solution 4.3

First reduce the base: $23 = 3 \cdot 7 + 2$ , so $23 \equiv 2 (mod 7)$ . Now $2 3^{85} \equiv 2^{85} (mod 7)$ . $p = 7$ , $g cd (2, 7) = 1$ , so $2^{6} \equiv 1$ . Reduce the exponent mod $6$ : $85 = 6 \cdot 14 + 1$ , so $2^{85} = (2^{6})^{14} \cdot 2^{1} \equiv 1 \cdot 2 = 2 (mod 7) .$ Answer: $2 3^{85} \equiv 2 (mod 7)$ .

Level 5 — Mastery

Reason about where FLT stops working and how it is generalized.

Recall Solution 5.1

(a) FLT is a one-way statement: " $p$ prime $\Rightarrow a^{p - 1} \equiv 1$ ." It says nothing about composite moduli. A composite $n$ may accidentally satisfy $a^{n - 1} \equiv 1 (mod n)$ ; here $341$ does so for $a = 2$ . That's a coincidence permitted by the theorem, not a violation. (b) The converse " $a^{n - 1} \equiv 1 (mod n) \Rightarrow n$ prime" is what a naive test would use — and it is false. $341$ is a counterexample (a Fermat pseudoprime to base $2$ ). See Carmichael Numbers for composites that fool every base. Practically: passing the test proves nothing on its own; failing it (some coprime $a$ with $a^{n - 1} \neq \equiv 1$ ) does prove compositeness. Answer: No contradiction; the converse is invalid, which is the whole reason single-base Fermat tests are unreliable.

Recall Solution 5.2

Take $a = 5$ (and $g cd (5, 6) = 1$ ). $5 \equiv - 1 (mod 6)$ , so $5^{5} \equiv (- 1)^{5} = - 1 \equiv 5 (mod 6)$ , which is not $1$ . So even with a coprime base, the classical exponent $n - 1 = 5$ fails when $n$ is composite. The correct exponent comes from Euler's theorem: $ϕ (6) = 2$ , and indeed $5^{2} = 25 \equiv 1 (mod 6)$ . Answer: $5^{5} \equiv 5 \neq \equiv 1 (mod 6)$ ; primality is essential.

Recall Solution 5.3

$ϕ (15) = ϕ (3) ϕ (5) = 2 \cdot 4 = 8$ , and $g cd (2, 15) = 1$ , so Euler guarantees $2^{8} \equiv 1 (mod 15)$ . Check: $2^{4} = 16 \equiv 1 (mod 15)$ already — the true order is $4$ , which divides the guaranteed $8$ (orders always divide the guaranteed exponent). Using $2^{4} \equiv 1$ : $100 = 4 \cdot 25, 2^{100} = (2^{4})^{25} \equiv 1^{25} = 1 (mod 15) .$ Answers: Euler guarantees $2^{8} \equiv 1$ ; and $2^{100} \equiv 1 (mod 15)$ .

Recall One-page skill checklist (self-test)

Before applying the classical form: ☐ Is $p$ prime? ☐ Is $g cd (a, p) = 1$ ? Reduce the base mod $p$ ::: yes, always shrink $a$ first Reduce the exponent mod $p - 1$ ::: only when $g cd (a, p) = 1$ ; period is $p - 1$ Exponent equals $p - 1$ ::: answer is $1$ Exponent equals $p$ ::: answer is $a$ (Form 2) Modular inverse of $a$ mod prime $p$ ::: $a^{p - 2} mod p$ Composite modulus $n$ ::: use Euler with $ϕ (n)$ , not FLT

Connections

Fermat's little theorem (statement) — the parent statement these exercises drill.
Modular Arithmetic Basics — remainders, congruence, reducing base and exponent.
Euler's Totient Function — the composite-modulus generalization used in L5.
Wilson's Theorem — a companion prime-only identity.
Carmichael Numbers — composites that fool the Fermat test for every base.
Multiplicative Group Modulo Prime — why the exponent cycle has length $p - 1$ .
Modular Exponentiation Algorithms — fast squaring used in the large-exponent problems.
RSA Cryptosystem — where modular inverses and FLT-style reasoning power real cryptography.