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

Printable View

- Jun 3rd 2010, 02:59 PMdwsmithInfinitely 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 PMchiph588@
- Jun 3rd 2010, 03:04 PMdwsmith
- Jun 3rd 2010, 03:07 PMchiph588@
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 PMdwsmith
- Jun 3rd 2010, 03:19 PMchiph588@
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 PMdwsmith
- Jun 3rd 2010, 05:33 PMchiph588@
Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)

- Jun 3rd 2010, 10:57 PMCaptainBlack
- Jun 3rd 2010, 11:46 PMBruno 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 AMmelese
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 AMaman_cc
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.