Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
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.
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 $\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)$.
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.
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.