Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
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.
Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)
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 .
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.
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.