A Novel Proof of the Infinitude of Primes Revisited

Daniel Cass Gerald Wildenberg

In this note we rephrase a proof of the infinitude of primes which appears in [1]. The original uses topological terminology which our approach avoids.

Definition: A set S of integers is periodic if for some p we have that n ∈ S if and only if n+p ∈ S. We call the smallest positive such p the period of S.

Observe that if S and T are periodic sets with periods s and t respectively then S U T is periodic with period dividing the least common multiple of s and t. We can use induction to show that any finite union of periodic sets is periodic. Also observe that if S is periodic, then the complement of S is periodic.

Theorem: There are infinitely many prime integers.

Proof: Let S = U { S_p : p prime }, where S_p={n·p : n ∈ Z}.

Clearly each S_p is a periodic set. If the collection of primes is finite then the union above is over a finite set. But then S is periodic and thus so is its complement. However the complement of S is {-1,1}, which being finite is not periodic. This contradiction lets us conclude that the above union could not be a finite union. Thus the number of primes is infinite. █

References:

1. H. Fürstenberg, "On the infinitude of primes," Amer. Math. Monthly, 62 (1955) 353.