There are infinitely many primes

Day 1

Proof of Lemma 1. Let n \ge 2. The divisors of n greater than 1 include n itself and all lie among the finitely many integers 2, 3, \ldots, n, so there is a least one, d. Suppose, for contradiction, that d is not prime. Then d = ab with 1 < a < d. Since a \mid d and d \mid n, the transitive property of divisibility gives a \mid n. So a is a divisor of n greater than 1 and less than d, contradicting the choice of d. So d is prime. \square

Finding a least element was safe because the set was finite. Every nonempty set of positive integers has a least element, finite or not; that principle, well-ordering, belongs to Strong induction and well-ordering.

Proof of Theorem 1. Let N = p_1 p_2 \cdots p_k + 1. Each p_i \ge 2, so N \ge 3, and by Lemma 1 N has a prime divisor. Let q be any prime divisor of N, and suppose, for contradiction, that q = p_i for some i. Then q divides the product p_1 p_2 \cdots p_k, being one of its factors, and q divides N. A divisor of two integers divides their difference (Proving statements about divisibility), so

But no integer greater than 1 divides 1. So q is not on the list. \square

This is a direct construction: from any list it produces a prime off it. The contradiction inside is only the small step showing q differs from each p_i.

Proof of Theorem 2. Suppose, for contradiction, that there are only finitely many primes, and list all of them: p_1, \ldots, p_k. By Theorem 1 some prime is not on this list, yet the list held every prime. So the set of primes is infinite. \square

Day 2

Proof of Lemma 2. Let x = 4a + 1 and y = 4b + 1 with a, b integers. Then

and 4ab + a + b is an integer. For more factors, multiply them in one at a time: each partial product has the form 4k + 1, so the two-factor case applies again. \square

Proof of Lemma 3. Let N be a positive integer of the form 4k + 3. Its divisors of the form 4k + 3 include N and lie among 1, \ldots, N, so there is a least one, d \ge 3. Suppose, for contradiction, that d is not prime: d = ab with 1 < a, b < d. Since d is odd, so are a and b (a product with an even factor is even, Proving statements about even and odd numbers). An odd integer leaves remainder 1 or 3 on division by 4. If a and b both had the form 4k + 1, so would d, by Lemma 2, and an integer has only one remainder on division by 4. So one of them, say a, has the form 4k + 3. Then a \mid d and d \mid N, so a is a divisor of N of the form 4k + 3 smaller than d, a contradiction. So d is prime. \square

Proof of Theorem 3. Suppose, for contradiction, that the primes of the form 4k + 3 are finitely many, and list them all: q_1, \ldots, q_m. The list is not empty, since 3 = 4 \cdot 0 + 3. Let

Then N = 4(q_1 q_2 \cdots q_m - 1) + 3 has the form 4k + 3, and N \ge 11. By Lemma 3, N has a prime divisor q of the form 4k + 3, which must be some q_i. Then q divides 4 q_1 \cdots q_m and N, so q \mid 4 q_1 \cdots q_m - N = 1, which is impossible. \square

Why the same proof fails for 4k + 1. List the primes r_1, \ldots, r_m of the form 4k + 1 and take N = 4 r_1 \cdots r_m + 1, of the form 4k + 1. The proof would need an analog of Lemma 3, that an integer of the form 4k + 1 has a prime divisor of that form. That is false: a product of two integers of the form 4k + 3 has the form 4k + 1 (Exercise 17), so every prime factor of N can be of the form 4k + 3 (Example 5). The theorem for 4k + 1 is true, but its proof needs a different number and facts from Modular arithmetic.

Proof of Theorem 4. Write P_n = p_1 p_2 \cdots p_n.

First, p_{n+1} \le P_n + 1. By Theorem 1, P_n + 1 has a prime divisor q that is not among p_1, \ldots, p_n. A positive divisor of a positive integer is at most that integer, so q \le P_n + 1, and q is a prime other than the first n, so q \ge p_{n+1}.

Next, P_n \le 2^{2^n - 1} for every n \ge 1, by induction. For n = 1, P_1 = 2 = 2^1. Assume P_n \le 2^{2^n - 1}. Since 1 \le 2^{2^n - 1},

and so P_{n+1} = P_n \, p_{n+1} is at most 2^{2^n - 1} \cdot 2^{2^n}, which is 2^{2^{n+1} - 1}. That completes the induction. The display above is the theorem for n + 1 \ge 2, and p_1 = 2 = 2^{2^0} is the case n = 1. \square

1. 106 = 2 \cdot 53, and 53 is prime (2, 3, 5, 7 do not divide it, and 8^2 > 53). Neither 2 nor 53 is on the list.
2. Yes. It is 43, not divisible by 2, 3 or 5, and 7^2 > 43.
3. 5 \cdot 11 + 1 = 56 = 2^3 \cdot 7. The prime divisors 2 and 7 are off the list and both smaller than 11; 2 is smaller than 5 too.
4. 43. No prime from 2 to 41 divides 2021, and 2021 = 43 \cdot 47. It is prime by Lemma 1, or directly: 2, 3, 5 do not divide 43, and 7^2 > 43.
5. 7! + 1 = 5041 = 71^2, so the only prime divisor is 71 > 7.
6. 210 - 1 = 209 = 11 \cdot 19. Both primes are off the list 2, 3, 5, 7, as Example 3 says.
7. N = p_i Q + 1, with Q the product of the other primes. Since 0 \le 1 < p_i, the remainder is 1.
8. If d \mid m and d \mid m + 1, then d divides (m + 1) - m = 1, but no integer d \ge 2 divides 1. \square
9. For n \ge 3, n! - 1 \ge 5 has a prime divisor q. If q \le n, then q \mid n! and q \mid n! - (n! - 1) = 1, impossible; so q > n. Every n \ge 3 thus has a prime above it, so there is no largest prime. At n = 2, 2! - 1 = 1 has no prime divisor.
10. Not being divisible by the listed primes does not rule out an unlisted prime divisor. For the list 3, 5: 3 \cdot 5 + 1 = 16 = 2^4, not prime.
11. If the primes were finite, list them all; Theorem 1 gives a prime off that list, a contradiction. Theorem 1 also says where to find a missing prime: among the prime divisors of p_1 \cdots p_k + 1.
12. By Theorem 1 a prime divisor q is not among p_1, \ldots, p_k, which are all the primes up to p_k. So q > p_k. \square
13. 1989 = 4 \cdot 497 + 1, by Lemma 2, since 9 = 4 \cdot 2 + 1, 13 = 4 \cdot 3 + 1 and 17 = 4 \cdot 4 + 1. (Lemma 2 does not need prime factors.)
14. N = 4 \cdot 399 - 1 = 1595 = 5 \cdot 11 \cdot 29. The prime 11 = 4 \cdot 2 + 3 is off the list; 5 and 29 have the form 4k + 1.
15. 261 = 3^2 \cdot 29, and 29 = 4 \cdot 7 + 1 is new. No rescue: a proof must work for every list, and Example 5 is a list where no such prime appears.
16. Bounds: 2, 4, 16, 256, 65{,}536 and 2^{32} = 4{,}294{,}967{,}296, against p_n = 2, 3, 5, 7, 11, 13. The least such n is n = 6.
17. (4a + 3)(4b + 3) expands to 16ab + 12a + 12b + 9, which is 4(4ab + 3a + 3b + 2) + 1 with 4ab + 3a + 3b + 2 an integer. \square
18. (6a + 1)(6b + 1) expands to 36ab + 6a + 6b + 1, which is 6(6ab + a + b) + 1 with 6ab + a + b an integer. \square
19. Suppose the primes of the form 6k + 5 are r_1, \ldots, r_m (5 is one). Let N = 6 r_1 \cdots r_m - 1, which is 6(r_1 \cdots r_m - 1) + 5. Neither 2 nor 3 divides N, so neither divides any divisor of N; and an integer with remainder 0, 2, 3 or 4 on division by 6 is divisible by 2 or 3, so every divisor of N has the form 6k + 1 or 6k + 5. Let d be the least divisor of N of the form 6k + 5. If d = ab with 1 < a, b < d, Exercise 18 forces one factor to have the form 6k + 5, smaller than d, a contradiction. So d is prime, d = r_i, and d \mid 6 r_1 \cdots r_m - N = 1, impossible. \square
20. By Example 2 with n = p_n, a prime divisor q of p_n! + 1 has q > p_n, and q \le p_n! + 1. A prime above p_n is at least p_{n+1}, so p_{n+1} \le q \le p_n! + 1. \square
21. With 3 listed, 3 divides 4 q_1 \cdots q_m and 3, so 3 \mid N, and Lemma 3’s prime may be 3 itself. For 3, 7: 4 \cdot 21 + 3 = 87 = 3 \cdot 29, and 29 has the form 4k + 1. Repair: N = 4Q + 3, with Q the product of the listed primes other than 3 (Q = 1 if none). Each prime in Q leaves remainder 1 or 2 on division by 3, and so does a product of such integers (expand as in Lemma 2), so 3 \nmid Q. If 3 \mid N, then 3 \mid N - 3 = 4Q = 3Q + Q, so 3 \mid Q, impossible. If another q_i \mid N, then q_i \mid N - 4Q = 3, impossible. So Lemma 3’s prime is off the list.
22. Every integer has the form 4k, 4k + 1, 4k + 2 or 4k + 3 (The division algorithm). 4k = 2(2k) and 4k + 2 = 2(2k + 1) are even, and the only even prime is 2. \square