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@
- 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 primes, the greatest being .

Half of the integers are not divisible by 2.

Two-thirds of those are not divisible by .

Four fifths of those are not divisible by .

All the way to : ths are not divisible by .

Hence the "proportion" of integers not divisible by any one of is equal to , which is greater than , which is absurd because every integer must be a multiple of one of , which we've supposed to be the only primes.

The reasoning also shows informally that ; expanding the product yields a nice Dirichlet series for the Möbius function. Note also that the product is . - Jun 4th 2010, 04:35 AMmelese
There is a famous relationship due to Euler: (continues forever)

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: . In general, ).

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.