There are many proofs that there are infinitely many prime numbers. We present several proofs that are, possibly, new.
Furstenberg is famous for, among other things, a topological proof of the infinitude of primes [On the infinitude of primes, Amer. Math. Monthly 62, (1955) 353]. That proof also appears in Proofs from The Book by Aigner and Zeigler, as well as the survey paper Euclid’s Theorem on the Infinitude of Primes: A Historical Survey of its Proofs (300 B.C.- 2012) by Mestrovic [arXiv:1202.3670v2 [math.HO] 5 Jun 2012]. Furstenberg wrote his proof in 1955 when he was twenty. Our proof incorporates his basic idea (but is couched in terms of the continuous functions on the topological space considered by Furstenberg).
A sequence f(1), f(2), f(3), … is periodic if, for some integer P, f(n+P)=f(n) for all n. We say that P is a period of f.
The (coordinate-wise) sum of two periodic sequences is periodic:
To see this, suppose f and g are periodic with periods and respectively. Then
and so f+g is periodic.
Suppose now that there are only finitely many primes. For every prime p, let
be 1 if n is a multiple of p, 0 otherwise.
Let , a finite sum of periodic sequences.
Note that F(n)=0 if and only if n=1 since 1 is the only number with no prime factors.
Since F is periodic, F(n)=0 for infinitely many values of n, a contradiction.
A trim variant of this proof is as follows.
Let F(n) be the number of primes dividing n so, for example, F(1)=0, F(2)=1, F(60)=3, and F(15)=2.
Suppose there are only finitely many primes, and let P be the product of all of them. Then
F(n+P)=F(n) for every n
but F(n)=0 only if n=1 — a contradiction.
Here is a version of my proof appearing recently in the Monthly:
If there are only finitely many primes then
The next proof is probabilistic.
Suppose that there are only finitely many primes and let where are independent with the distribution .
Then X is well defined and obeys P(X is divisible by n)=1/n.
By the independence of , if , then
This is absurd, however, since