Infinitude of Primes Via *-Sets

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

(1)

ai - aj divides ai



for all distinct i and j. |X| denotes for the size of set X, e.g. |{a1, ..., an}| = 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 {a1, ..., an} is a *-set. Define b0 = a1·...·an, the product of all ak's, k = 1, ..., n. Let bk = b0 + ak, k = 1, ..., n. Then X = {bk: k = 0, ..., n} is a *-set and |X| = n + 1.

Lemma 2

Suppose {a1, ..., an} is a *-set of size n. For k = 1, ..., n, define fk = 2ak + 1. Then the numbers f1, ..., fn are mutually prime.

Proof

Assume there are fk and fm, fk > fm, divisible by the same odd prime p. Then p divides 2am(2ak - am - 1).

Since p is odd, it ought to divide 2ak - am - 1. Now, if s|t then 2s - 1 | 2t - 1; thus, by definition of the *-set, 2ak - am - 1 divides 2ak - 1. So that p | 2ak - 1. But also p | 2ak + 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

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

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71492502