Fermat's little theorem

Euclid’s lemma and the coprime factor lemma used below are proved in Bezout's identity and the extended Euclidean algorithm.

First proof of Theorem 1 (rearrangement). Suppose p \nmid a, and look at a, 2a, \dots, (p-1)a. None is 0 modulo p: if p \mid ka then by Euclid’s lemma p \mid k or p \mid a, and p \nmid k because 1 \le k \le p - 1. No two agree: \gcd(a, p) = 1, since the only positive divisors of p are 1 and p, so ia \equiv ja gives i \equiv j by Lemma 2, and two numbers from 1 to p - 1 that are congruent modulo p are equal. So the remainders of the p - 1 multiples are p - 1 different numbers from \{1, \dots, p - 1\}, which is all of them. Multiplying the two lists and using the multiplication rule,

Each factor of (p-1)! is below p, so by Euclid’s lemma (extended to many factors) p \nmid (p-1)!, and \gcd((p-1)!, p) = 1. Lemma 2 cancels it: a^{p-1} \equiv 1. Multiplying by a gives a^p \equiv a, which also holds when p \mid a because both sides are 0. \square

Proof of Lemma 3. \binom{p}{k} counts the k-element subsets of a p-element set, so it is an integer, and \binom{p}{k} \cdot k! \, (p-k)! = p! (Combinations). The prime p divides p!. Every factor of k! and of (p-k)! lies between 1 and p - 1, so by Euclid’s lemma p divides neither. Euclid’s lemma applied to the left side then gives p \mid \binom{p}{k}. \square

Second proof of Theorem 1 (induction). First let a \ge 0 and induct on a (Proof by induction). For a = 0, 0^p = 0. Suppose a^p \equiv a. By the binomial theorem (The binomial theorem),

Each middle term is a multiple of p by Lemma 3, so (a+1)^p \equiv a^p + 1 \equiv a + 1. That proves a^p \equiv a for all a \ge 0. A negative a is congruent to r = a \bmod p \ge 0, so a^p \equiv r^p \equiv r \equiv a by Corollary 4 of Congruence modulo n and its arithmetic. If p \nmid a, then a \cdot a^{p-1} \equiv a \cdot 1 and Lemma 2 cancels a. \square

Proof of Corollary 4. Say e \ge f, so e = f + (p-1)m with m \ge 0. Then a^e = a^f (a^{p-1})^m, which is \equiv a^f \cdot 1^m = a^f. The exponents e with a^e \equiv 1 are exactly the multiples of the order (Powers modulo n), and p - 1 is one. \square

Corollary 5 is Theorem 1 with a^{p-1} written as a \cdot a^{p-2}, and Corollary 6 is the contrapositive of Theorem 1 (A conditional and its contrapositive), since a number n \ge 2 that is not prime is composite.

Proof of Theorem 7. For n = 1 every congruence holds. Let n \ge 2 and let r_1, \dots, r_k be the integers from 1 to n coprime to n, so k = \varphi(n). Let s_i be the remainder of a r_i. If a prime q divided both s_i and n, it would divide a r_i, which is s_i plus a multiple of n, so by Euclid’s lemma q \mid a or q \mid r_i, against \gcd(a, n) = \gcd(r_i, n) = 1. So s_i is coprime to n, and s_i \ne 0 because \gcd(0, n) = n > 1. Each s_i is therefore one of the r_j, and the s_i are different by Lemma 2. They are the r_j rearranged, so with R = r_1 \cdots r_k, a^k R \equiv R \pmod{n}. By the same prime argument \gcd(R, n) = 1, and Lemma 2 cancels R. \square

When n = p is prime, \varphi(p) = p - 1 and the proof is the first proof of Theorem 1.

1. 3. 2^{12} \equiv 1 and 100 = 12 \cdot 8 + 4, so 2^{100} \equiv 2^4 = 16 \equiv 3.
2. 6. 1000 = 18 \cdot 55 + 10, so 6^{1000} \equiv 6^{10}. 6^2 = 36 \equiv -2, 6^8 \equiv (-2)^4 = 16 \equiv -3, so 6^{10} \equiv (-3)(-2) = 6.
3. 6. 12 \equiv 5 and 12345 = 6 \cdot 2057 + 3, so the power is \equiv 5^3 = 125 = 17 \cdot 7 + 6.
4. 1. 3^{50} = 9^{25} and 9^2 = 81 \equiv 9 \pmod{12}, so 3^{50} \equiv 9 \pmod{12}. By Corollary 4 the power is \equiv 9^9, and 9^3 = 729 = 56 \cdot 13 + 1 gives 9^9 \equiv 1.
5. 10. Each k from 1 to 10 has 11 \nmid k, so k^{10} \equiv 1, and the sum is \equiv 10.
6. The values are 11, 55, 165, 330, 462 and then the same five in reverse, all multiples of 11. But \binom{9}{3} = 84 = 9 \cdot 9 + 3: with 9 composite, the factor 3 of 9 sits in 3! and 6!, and Euclid’s lemma does not apply.
7. Proof. Let p be one of 2, 3, 5, 7, 13; then p - 1 is 1, 2, 4, 6 or 12, a divisor of 12. If p \mid n, both n^{13} and n are 0 modulo p. Otherwise n^{p-1} \equiv 1, so n^{12} = (n^{p-1})^{12/(p-1)} \equiv 1 and n^{13} \equiv n. The five distinct primes all divide n^{13} - n, and applying the coprime factor lemma one prime at a time, as in Example 3, gives 2730 \mid n^{13} - n. \square
8. Proof. By Theorem 1, (a + b)^p \equiv a + b, a^p \equiv a and b^p \equiv b, so (a+b)^p \equiv a + b \equiv a^p + b^p. \square
9. Proof. Let x = a^{(p-1)/2}, an integer power since p is odd. Then x^2 = a^{p-1} \equiv 1, so p \mid (x - 1)(x + 1), and by Euclid’s lemma p \mid x - 1 or p \mid x + 1. \square
10. a = 3: 3, 6, 1, 4, 7, 2, 5, a rearrangement of 1 to 7 (as \gcd(3, 8) = 1), so 3^7 \cdot 7! \equiv 7!. But 7! = 5{,}040 = 630 \cdot 8 \equiv 0, so it cannot be cancelled; indeed 3^2 = 9 \equiv 1 gives 3^7 \equiv 3. a = 2: 2, 4, 6, 0, 2, 4, 6, which hits 0 and repeats, because \gcd(2, 8) \ne 1.
11. Proof. 2^p = (1 + 1)^p = \sum_{k=0}^{p} \binom{p}{k} by the binomial theorem. The terms k = 0 and k = p are 1 each, and every other term is a multiple of p by Lemma 3, so 2^p \equiv 2. \square
12. 6. 3^4 = 81 \equiv -4, 3^8 \equiv 16 \equiv -1, so 3^{15} = 3^8 \cdot 3^4 \cdot 3^2 \cdot 3 is \equiv (-1)(-4)(9)(3) = 108 \equiv 6. Check: 3 \cdot 6 = 18 \equiv 1.
13. x \equiv 7 \pmod{19}. The inverse of 4 is 4^{17}: 4^2 \equiv -3, 4^4 \equiv 9, 4^8 \equiv 81 \equiv 5, 4^{16} \equiv 25 \equiv 6, 4^{17} \equiv 24 \equiv 5. Then x \equiv 5 \cdot 9 = 45 \equiv 7; check 4 \cdot 7 = 28 \equiv 9.
14. 64. 90 = 64 + 16 + 8 + 2; squares of 2 modulo 91: 2, 4, 16, 256 \equiv 74, 74^2 \equiv 16, 74, 16 for 2^1 to 2^{64}. Then 2^{90} \equiv 16 \cdot 16 \cdot 74 \cdot 4; 16 \cdot 16 \equiv 74, 74 \cdot 74 \equiv 16, 16 \cdot 4 = 64. Since 64 \ne 1 and 91 \nmid 2, Corollary 6 proves 91 composite.
15. 1105 is composite. If \gcd(a, 1105) = 1, Theorem 1 gives a^4 \equiv 1 \pmod{5}, a^{12} \equiv 1 \pmod{13}, a^{16} \equiv 1 \pmod{17}. As 1104 = 4 \cdot 276 = 12 \cdot 92 = 16 \cdot 69, a^{1104} \equiv 1 modulo each prime, and as in Example 6, 1105 \mid a^{1104} - 1.
16. 2^4 = 16 \equiv 1 \pmod{15}, so 2^{14} = (2^4)^3 \cdot 2^2 \equiv 4, not 1, and 15 \nmid 2. By Corollary 6, 15 is composite.
17. 7. \displaystyle \varphi(20) = 20 \cdot \frac{1}{2} \cdot \frac{4}{5} = 8, 2023 = 8 \cdot 252 + 7, and 3^7 = 2{,}187 \equiv 7.
18. 29. 36 = 2^2 \cdot 3^2, so \displaystyle \varphi(36) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12, and \gcd(5, 36) = 1. As 1001 = 12 \cdot 83 + 5, 5^{1001} \equiv 5^5 = 3{,}125 = 86 \cdot 36 + 29.
19. The integers are 1, 5, 7, 11, so \varphi(12) = 4. Times 5: 5, 25 \equiv 1, 35 \equiv 11, 55 \equiv 7, the same four rearranged, and 5^4 = 625 = 52 \cdot 12 + 1. Exponent 2 already works: 1, 25, 49, 121 are all \equiv 1.
20. Proof. Suppose q^{n-1} \equiv 1 \pmod{n}. Then n \mid q^{n-1} - 1, and q \mid n, so q \mid q^{n-1} - 1. Since n - 1 \ge 1, q \mid q^{n-1}, so q divides the difference 1, which is impossible. \square
21. Proof. By Corollary 4 the order divides 12, so it is 1, 2, 3, 4, 6 or 12. Now 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16 \equiv 3, 2^6 = 64 \equiv 12, none 1, so the order is 12. \square
22. Proof. p \nmid a, so a^{p-1} \equiv 1 \pmod{p}, so (a^{p-1})^{q-1} \equiv 1 \pmod{p}. Likewise modulo q. So p \mid m and q \mid m for m = a^{(p-1)(q-1)} - 1: m = pk, q \mid pk with \gcd(q, p) = 1, so q \mid k and pq \mid m. \square