PROOF 190

Prove.

Gaps between primes can be arbitrarily wide

On the natural numbers ℕ.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

k ∣ m means there is a natural number q with m = kq.

Proof.

Divisors and multiples are written with this one line.convention

∎

Definition D2

Let n! = 1 × 2 × ⋯ × n (n ≥ 2).

Proof.

Sums and products never leave the natural numbers, so n! ∈ ℕ and 0 < n!.A6, A5

∎

Definition D3

Among the natural numbers m ≥ 2, those having a divisor d with 1 < d < m are called composite, and those without one are called prime.

Proof.

Every natural number at least 2 is one of the two.convention

∎

Lemma L1

If 2 ≤ k ≤ n, then k ∣ n!.

Proof.

(1)k appears among the factors of 1 × 2 × ⋯ × n (since 2 ≤ k ≤ n).assumption, D2

(2)Pulling k to the front by commutativity and associativity, n! = k × m — m is the product of the remaining factors, a natural number.(1), A2, A6

(3)Therefore k ∣ n!.(2), D1

∎

Theorem T1

If 2 ≤ k ≤ n, then n! + k is composite.

Proof.

(1)k ∣ n! — that is, there is a natural number m with n! = km.L1, D1

(2)n! + k = km + k × 1 = k(m + 1).(1), A3, A1, E

(3)m + 1 ∈ ℕ, so k ∣ (n! + k).(2), A6, D1

(4)Adding 1 to both sides of 0 < 1 gives 1 < 2 ≤ k — k is greater than 1.A7, A4, A8, assumption

(5)Adding k to both sides of 0 < n! gives k < n! + k.D2, A4

(6)There is a divisor k with 1 < k < n! + k — n! + k is composite.(3), (4), (5), D3

∎

Corollary C

For arbitrary n, there is a run of n − 1 consecutive numbers containing no prime.

Proof.

(1)From n! + 2 to n! + n is a run of n − 1 consecutive natural numbers.D2, A6

(2)Each term n! + k (2 ≤ k ≤ n) is composite.T1

(3)Therefore a prime-free run of length n − 1 exists. There is no restriction on n.(1), (2), D3

(4)There are infinitely many primes (Proof 11). They never end, yet the gaps between them widen without bound.(3), A9

∎

Remark

Can A1 be removed from this proof?

That n! + k is composite hangs on a single factoring. Find that line.