Fermat's little theorem
Tonight's idea
Write \(a \equiv b \pmod{n}\) when \(a\) and \(b\) leave the same remainder on division by \(n\). You can add, subtract and multiply congruences like equations. (The grade 6 clock arithmetic sheet is the gentle version.)
Powers of 2 mod 7: \(2, 4, 1, 2, 4, 1, \ldots\) Powers of 3 mod 7: \(3, 2, 6, 4, 5, 1, \ldots\) Both are back at 1 by the sixth power. That is no accident.
Fermat's little theorem. If \(p\) is prime and \(a\) is not a multiple of \(p\), then \(a^{p-1} \equiv 1 \pmod p\). Equivalently, \(a^p \equiv a \pmod p\) for every whole number \(a\).
Proof. Look at \(a, 2a, \ldots, (p-1)a\) mod \(p\). None is 0, and no two are equal: if \(ia \equiv ja\) then \(p\) divides \((i-j)a\), so \(p\) divides \(i - j\) (a prime that divides a product divides one of the factors), impossible when \(0 \lt |i-j| \lt p\). So these are \(1, 2, \ldots, p-1\) in a shuffled order (mod 7 with \(a = 3\), see the table). Multiply them all: \(a^{p-1}(p-1)! \equiv (p-1)! \pmod p\). Since \(p\) does not divide \((p-1)!\), it must divide \(a^{p-1} - 1\). ∎
| \(k\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(3k \bmod 7\) | 3 | 6 | 2 | 5 | 1 | 4 |
The theorem shrinks huge powers, tests primes, and drives RSA encryption, tomorrow night.
Watch one: \(2^{100}\) mod 7
Fermat says \(2^6 \equiv 1 \pmod 7\), so every block of six 2s is worth 1. Divide: \(100 = 6 \times 16 + 4\). Then \(2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 2 \pmod 7\).
The recipe, when \(a\) is not a multiple of \(p\): reduce the exponent mod \(p - 1\), then compute the small power. Reduce the exponent mod \(p - 1\), not mod \(p\): that is the classic slip. The condition matters too: \(7^6 \equiv 0 \pmod 7\), but blindly reducing the exponent would give \(7^0 = 1\).
Your turn
- Find the remainders of \(5^{20}\) divided by 7, of \(10^{18}\) divided by 19, and of \(2^{35}\) divided by 13.
- What is the last digit of \(7^{2026}\)? 10 is not prime, so Fermat does not apply directly. Use mod 5 (where it does) and the fact that \(7^{2026}\) is odd.
- Fermat gives a primality test: pick a base \(a\) with \(1 \le a \le n - 1\), compute \(a^{n-1} \bmod n\), and if the answer is not 1 then \(n\) is definitely composite. (a) Show that \(2^{340} \equiv 1 \pmod{341}\), even though \(341 = 11 \times 31\) is composite. (Hint: \(2^{10} = 1024 = 3 \times 341 + 1\).) (b) What does this say about the test with base 2? (c) Why does base 3, with \(3^{340} \equiv 56 \pmod{341}\), catch it?
- Prove that \(n^5 - n\) is divisible by 30 for every whole number \(n\). (Use \(a^p \equiv a\) for \(p = 2, 3, 5\); for \(p = 3\) write \(n^5 = n^3 \cdot n^2\).)
The times tables on a circle demo draws the multiplication-by-\(a\) shuffle from the proof: set \(n\) to a prime, pick a multiplier that is not a multiple of it, and watch every point get hit exactly once.
Stretch: a lock made of remainders
Euler's version: if \(\varphi(n)\) counts the numbers from 1 to \(n\) coprime to \(n\) (sharing no factor with \(n\) except 1), then \(a^{\varphi(n)} \equiv 1 \pmod n\) for \(a\) coprime to \(n\). Here \(\varphi(15) = 8\). Encrypt \(m = 2\) as \(c = m^3 \bmod 15\), then decrypt as \(c^3 \bmod 15\). Why does \(m\) come back?
Answers
- \(5^6 \equiv 1 \pmod 7\) and \(20 = 6 \cdot 3 + 2\), so \(5^{20} \equiv 25 \equiv 4\). \(10^{18} \equiv 1 \pmod{19}\) directly. \(2^{12} \equiv 1 \pmod{13}\) and \(35 = 12 \cdot 2 + 11\), so \(2^{35} \equiv 2^{11} = 2048 = 13 \cdot 157 + 7 \equiv 7\).
- Mod 5: \(7^4 \equiv 1\), and \(2026 = 4 \cdot 506 + 2\), so \(7^{2026} \equiv 49 \equiv 4 \pmod 5\). The last digit is 4 or 9; the number is odd, so it is 9.
- (a) \(2^{10} \equiv 1 \pmod{341}\), so \(2^{340} = (2^{10})^{34} \equiv 1\). (b) The test with base 2 says "maybe prime" and is wrong: a passing base is only evidence. (c) Base 3 gives 56, not 1, so 341 is exposed: a single failing base is proof.
- \(n^5 \equiv n \pmod 5\) by Fermat. Mod 3: \(n^3 \equiv n\), so \(n^5 = n^3 n^2 \equiv n^3 \equiv n\). Mod 2: \(n^2 \equiv n\), so \(n^5 \equiv n\). Thus \(n^5 - n\) is divisible by 2, 3 and 5, hence by 30.
Stretch. \(2^3 = 8\), so \(c = 8\). Then \(8^3 = 512 = 34 \cdot 15 + 2\), so 2 comes back. In general \(3 \cdot 3 = 9 = 1 + 8\), so \(c^3 = m^9 = m \cdot m^{8} \equiv m \cdot 1 = m\). Euler's theorem is the reason the lock opens, and tomorrow this becomes RSA with primes hundreds of digits long.