Infinitude of Primes Via *-Sets

A *-set is a finite set of positive integers {a₁, ..., a_n} such that

(1)	a_i - a_j divides a_i

for all distinct i and j. |X| denotes for the size of set X, e.g. |{a₁, ..., a_n}| = n.

Lemma 1

For all n ≥ 2, there is a *-set of size n.

Proof

The proof is by induction. |{1, 2}| = 2 and obviously {1, 2} is a *-set.

Suppose {a₁, ..., a_n} is a *-set. Define b₀ = a₁·...·a_n, the product of all a_k's, k = 1, ..., n. Let b_k = b₀ + a_k, k = 1, ..., n. Then X = {b_k: k = 0, ..., n} is a *-set and |X| = n + 1.

Lemma 2

Suppose {a₁, ..., a_n} is a *-set of size n. For k = 1, ..., n, define f_k = 2^{^a_k} + 1. Then the numbers f₁, ..., f_n are mutually prime.

Proof

Assume there are f_k and f_m, f_k > f_m, divisible by the same odd prime p. Then p divides 2^{^a_m}(2^{^{a_k - a_m}} - 1).

Since p is odd, it ought to divide 2^{^{a_k - a_m}} - 1. Now, if s|t then 2^s - 1 | 2^t - 1; thus, by definition of the *-set, 2^{^{a_k - a_m}} - 1 divides 2^{^a_k} - 1. So that p | 2^{^a_k} - 1. But also p | 2^{^a_k} + 1. We conclude that p|2 which contradicts the assumption of p being an odd prime.

Theorem

There exists an infinite number of primes.

Proof

By lemmas 1 and 2, for any N, there is a set of N mutually prime terms and, therefore, the same number of distinct primes. Thus the assumption that the number of primes is finite would lead to a contradiction.

Reference

M. Gilchrist, A Proof That There Are an Infinite Number of Rational Primes, Am Math Monthly, 114 (August-September 2007), p. 622

Infinitude of Primes

40614917