some (new) proofs of the infinitude of primes

There are many proofs that there are infinitely many prime numbers.   We present several proofs that are, possibly, new.   

1)

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:

(1,2,1,2,1,2,1,2,1,2,1,2,…)+ (2,4,5,2,4,5,2,4,5,2,4,5…)=(3,6,6,4,5,7,3,6,6,4,5,7,…).

To see this,  suppose f and g are periodic with periods P_1  andP_2 respectively.  Then

(f+g)(n+P_1P_2)=f(n+\underbrace{P_1+...+P_1}_{P_2 \text{ times }})+g(n+\underbrace{P_2+...+P_2}_{P_1 \text{ times }})

=f(n)+g(n)=(f+g)(n) and so f+g is periodic.

Suppose now that there are only finitely many primes.  For every prime p, let

f_p(n) be 1 if n is a multiple of p,  0 otherwise.

Let F(n):=\sum_p f_p(n), 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.

2)

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.

3)

Here is a version of my proof appearing recently in the Monthly:

If there are only finitely many primes then

0=\displaystyle\prod_p \sin\left(\pi\dfrac{1+2\prod_{p'} p'}{p}\right)=\displaystyle\prod_p \sin\left(\dfrac{\pi}{p}\right)>0.

4)

The next proof is probabilistic. 

Suppose that there are only finitely many primes and let X=2^{T_2}\cdot 3^{T_3} \cdot 5^{T_5}\cdots where T_2, T_3, T_5,... are independent with the distribution P(T_p=n)=\dfrac{p-1}{p^{n+1}}.    

   Then X is well defined and obeys P(X is divisible by n)=1/n.

By the independence of T_p , if n=2^{a_2}3^{a_3}5^{a_5}\cdots, then 

P(X=n)=P(T_2=a_2)\cdot P(T_3=a_3)\cdot P(T_5=a_5)\cdots

=\prod_p \dfrac{p-1}{p^{a_p+1}}=\prod_p \dfrac 1{p^{a_p}}\dfrac{p-1}{p}=\dfrac1n\prod_p \dfrac{p-1}p.

This is absurd, however, since

1=\sum_n P(X=n)=\prod_p \dfrac{p-1}p\cdot \sum_n\frac1n=\infty.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s