Infinitude of Primes Via *-Sets

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


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.


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.


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.


There exists an infinite number of primes.


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.


  1. M. Gilchrist, A Proof That There Are an Infinite Number of Rational Primes, Am Math Monthly, 114 (August-September 2007), p. 622
[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]