# Infinitely many primes

• Jun 3rd 2010, 02:59 PM
dwsmith
Infinitely many primes
Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
• Jun 3rd 2010, 03:00 PM
chiph588@
Quote:

Originally Posted by dwsmith
Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?

A famous way is to show $\displaystyle \sum_{p \text{ prime}}\frac1p$ diverges.
• Jun 3rd 2010, 03:04 PM
dwsmith
Quote:

Originally Posted by chiph588@
A famous way is to show $\displaystyle \sum_{p \text{ prime}}\frac1p$ diverges.

That harmonic series of course diverges since p=1 but I am confused on how showing divergence proves there are infinitely many primes.
• Jun 3rd 2010, 03:07 PM
chiph588@
Quote:

Originally Posted by dwsmith
That harmonic series of course diverges since p=1 but I am confused on how showing divergence proves there are infinitely many primes.

This isn't the harmonic series. We're only summing over the prime numbers. i.e. $\displaystyle \sum_{p \text{ prime}}\frac1p = \frac12+\frac13+\frac15+\frac17+\frac{1}{11}+\frac {1}{13}+\cdots$

This proves infinitely many primes because if there were only finitely many primes, then $\displaystyle \sum_{p \text{ prime}}\frac1p$ couldn't possibly diverge.
• Jun 3rd 2010, 03:12 PM
dwsmith
Quote:

Originally Posted by chiph588@
This isn't the harmonic series. We're only summing over the prime numbers. i.e. $\displaystyle \sum_{p \text{ prime}}\frac1p = \frac12+\frac13+\frac15+\frac17+\frac{1}{11}+\frac {1}{13}+\cdots$

This proves infinitely many primes because if there were only finitely many primes, then $\displaystyle \sum_{p \text{ prime}}\frac1p$ couldn't possibly diverge.

Is there a specific test I would use then show divergence and hence conclude there are infinitely many primes?
• Jun 3rd 2010, 03:19 PM
chiph588@
Quote:

Originally Posted by dwsmith
Is there a specific test I would use then show divergence and hence conclude there are infinitely many primes?

Proof that the sum of the reciprocals of the primes diverges - Wikipedia, the free encyclopedia

I don't really like this proof because the first step takes the log of infinity, but it will give you the right idea and can be tweaked a bit to be valid.
• Jun 3rd 2010, 03:26 PM
dwsmith
Quote:

Originally Posted by chiph588@
Proof that the sum of the reciprocals of the primes diverges - Wikipedia, the free encyclopedia

I don't really like this proof because the first step takes the log of infinity, but it will give you the right idea and can be tweaked a bit to be valid.

I don't really like any of those.
• Jun 3rd 2010, 05:33 PM
chiph588@
Quote:

Originally Posted by dwsmith
I don't really like any of those.

Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)
• Jun 3rd 2010, 10:57 PM
CaptainBlack
Quote:

Originally Posted by dwsmith
Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?

Euclid's proof can be modified into a constructive proof that there is no largest prime.

CB
• Jun 3rd 2010, 11:46 PM
Bruno J.
Here's a proof I thought about a while back (which probably exists elsewhere!). It's not rigorous, as one doesn't really make precise the idea of putting "half" of the integers in a set. However, it's still an interesting reasoning.

Suppose there are only $\displaystyle n$ primes, the greatest being $\displaystyle p$.
Half of the integers are not divisible by 2.
Two-thirds of those are not divisible by $\displaystyle 3$.
Four fifths of those are not divisible by $\displaystyle 5$.
All the way to : $\displaystyle (p-1)/p$ths are not divisible by $\displaystyle p$.

Hence the "proportion" of integers not divisible by any one of $\displaystyle 2, 3, \dots, p$ is equal to $\displaystyle \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\dots \left(1-\frac{1}{p}\right)$, which is greater than $\displaystyle 0$, which is absurd because every integer must be a multiple of one of $\displaystyle 2, 3, \dots, p$, which we've supposed to be the only primes.

The reasoning also shows informally that $\displaystyle \prod_{p}\left(1-\frac{1}{p}\right)=0$; expanding the product yields a nice Dirichlet series for the Möbius $\displaystyle \mu$ function. Note also that the product is $\displaystyle 1/\zeta(1)$.
• Jun 4th 2010, 04:35 AM
melese
There is a famous relationship due to Euler: $\displaystyle 1+\frac12+\frac13+\dots$(continues forever)$\displaystyle =(1+\frac12+\frac1{2^2}+\dots)\times(1+\frac13+\fr ac1{3^2}+\dots)\times\dots\times(1+\frac1p+\frac1{ p^2}+\dots)\times\dots$

The left-hand side is the harmonic series that diverges. The right-hand side is a product in which each member is of finte value (for example:$\displaystyle 1+1/2+1/2^2+\dots=2, 1+1/3+1/3^3+\dots=3/2$. In general, $\displaystyle 1+1/p+1/p^2+\dots=p/(p-1)$).

The right-hand side, then must be an infinte product because the harmonic series is divergent.
• Jun 4th 2010, 05:43 AM
aman_cc
Quote:

Originally Posted by chiph588@
Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)

This was beautiful ! Thanks

I have a much less consequential question (related to the approach used in the Goldbach's proof)

Let a,b be co-prime

Let
a1 = a
a2 = a1 + b
a3 = a1a2 + b
a4 = a1a2a3 + b
....
...
.

Prove that (ai,aj) are also co-prime for any i and j

Now I struggled with this one - finally could do it using induction. But I'm looking for a better way to do it? Can anyone help plz? I will be more than happy to submit my proof if anyone needs to see that.