Fermat's Theorem

Fermat's Theorem

1. Statement (beginner words!)

If $p$ is prime and $a$ is NOT a multiple of $p$, then:

Corolary (works for ALL $a$):

In words: powers cycle back to 1 every $p-1$ steps mod prime!

2. Worked Examples (exam numericals!)

p = 5, a = 2: 2⁴ = 16, 16 mod 5 = 1 ✓
p = 7, a = 3: 3⁶ = 729, 729 mod 7 = 1 ✓ (729 = 7×104 + 1!)
shortcut: 2¹⁰⁰ mod 7? 100 = 6×16 + 4 → 2¹⁰⁰ = (2⁶)¹⁶ × 2⁴ ≡ 1¹⁶ × 16 ≡ 2 mod 7!

3. Why Crypto Cares

• Primality hint: if $a^{n-1}$ mod $n ≠ 1$ for some $a$, then $n$ is COMPOSITE (Fermat test base!).
• Inverse shortcut:

(used in RSA key gen!).

• Powers reduce exponents mod $p-1$ (fast mental math!).

4. Traps

• Needs PRIME $p$! ($2⁴$ mod $4 = 0$, not 1 — 4 composite, theorem fails!).
• Needs $a$ coprime to $p$ ($a$ multiple of $p$ → 0, not 1!).
• Converse FALSE: some composites pass for all coprime $a$ (Carmichael numbers, e.g. 561 — need Miller-Rabin!).

5. Exam Points

• State + verify ($2⁴$ mod $5$) — 5 marks, very frequent.
• Exponent-reduction numerical ($2¹⁰⁰$ mod $7$) — 5 marks, favourite.
• Carmichael caveat — 3 marks, frequent viva.