5
$\begingroup$

I've seen Euclid's proof of infinitely many primes, what are other approaches to proving there are infinitely many primes?

$\endgroup$
6
  • $\begingroup$ I googled "infinitely many primes" and found this $\endgroup$
    – user88595
    Jun 13, 2014 at 22:04
  • $\begingroup$ @BalarkaSen Is that a product over primes? How did the summation turn into that? $\endgroup$
    – user45572
    Jun 13, 2014 at 22:08
  • 2
    $\begingroup$ $$\sum_{n=1}^\infty \frac1n = \prod_p \left ( 1 - \frac1p \right )^{-1}$$ The harmonic series diverges. $$\sum_{n=1}^\infty \frac1{n^2} = \pi^2/6 = \prod_p \left ( 1 - \frac1{p^2} \right)^{-1}$$ $\pi^2$ is irrational. Plus, if you forgive me the cheek $$\sum_{n=1}^\infty \frac{1}{n^3} = \prod_p \left ( 1 - \frac1{p^3}\right)^{-1}$$ $\zeta(3)$ is irrational too. $\endgroup$ Jun 13, 2014 at 22:09
  • $\begingroup$ @user45572 See Euler product $\endgroup$ Jun 13, 2014 at 22:09
  • $\begingroup$ @BalarkaSen I know pi is irrational, why does that imply you can write it as a product over primes? $\endgroup$
    – user45572
    Jun 13, 2014 at 22:10

6 Answers 6

6
$\begingroup$

Here's another proof.I thought of it a while ago, and posted it as an answer to a mathoverflow question, but I don't imagine I was the first to think of it. The idea is not to rely on the fact that $\pi$ is irrational. Let $\mathcal{P}$ denote the set of primes. We have $\sum_{n=1}^{\infty} \frac{1}{n^{2}} = \frac{\pi^{2}}{6}$ and $\sum_{n=1}^{\infty} \frac{1}{n^{4}} = \frac{\pi^{4}}{90}.$ The first equation yields, $\prod_{p \in \mathcal{P}}\frac{p^{2}}{p^{2}-1} = \frac{\pi^{2}}{6}$ and the second leads to $\prod_{p \in \mathcal{P}}\frac{p^{4}}{p^{4}-1} = \frac{\pi^{4}}{90}.$ If we square the first of the last two equations and divide by the second, we obtain $\prod_{p \in \mathcal{P}}\frac{p^{2}+1}{p^{2}-1} = \frac{5}{2}.$ If $\mathcal{P}$ was finite, the left hand expression would be a rational number whose numerator was not divisible by $3$, but whose denominator was divisible by $3$ (because $p^{2}+1 \equiv 2$ (mod $3$) for every prime other than $3$, and $p^{2}-1$ is divisible by $3$ for every prime other than $3$). However, no such rational number could be equal to $\frac{5}{2},$ a contradiction.

$\endgroup$
1
  • $\begingroup$ (+1)This is one fun proof! Interestingly, irrationality of $\pi$ gives much stronger result than infinitude of primes $$\frac{\pi}{4} = \sum_{n= 0}^\infty \frac{(-1)^n}{2n+1} = \prod_{p \equiv 1(4)} \frac{p}{p-1} \cdot \prod_{p \equiv 3(4)} \frac{p}{p+1}$$ Thus at least one of the class $1\pmod{4}$ or $3\pmod{4}$ contains infinitely many primes. $\endgroup$ Jun 17, 2014 at 9:52
5
$\begingroup$

$$\prod_k \frac 1 {1-p_k^{-2}}=\sum_n n^{-2}=\zeta(2)=\frac {\pi^2}6,$$ and $\pi^2$ is irrational (from my favorite math resource) so we need infinitely many primes...

$\endgroup$
0
5
$\begingroup$

The prime harmonic series $\frac 1 2 + \frac 1 3 + \frac 1 5 + \ldots$ diverges.

$\endgroup$
2
  • $\begingroup$ Isn't the fact that it diverges dependent on there being infinitely many primes in the first place? How else could the discussion of divergence even occur otherwise? $\endgroup$
    – Axoren
    Jan 10, 2017 at 3:12
  • $\begingroup$ @Axoren: This is done formally by considering the sum of the reciprocals of all primes less than n for each n. These sums define a sequence (which would eventually be constant if there were finitely many primes), and you can show that the n-th sum is bounded below by $\log\log n - (\text{constant})$ where the constant is independent of n. Hence these sums tend to infinity (and, by definition, the corresponding series diverges). $\endgroup$
    – Dan
    Jan 10, 2017 at 4:11
5
$\begingroup$

Here is one of my favorites: $f(n) = 2^{2^{n}}+2^{2^{n-1}}+1, n \in \mathbb{N}$ has $n$ different prime factors. Prove by induction.

$\endgroup$
1
  • 1
    $\begingroup$ I think $2^{2^{n}}-1$ has the same property ( ie, at least $n$ different prime factors). $\endgroup$ Jun 13, 2014 at 23:02
1
$\begingroup$

There is a topological proof: http://en.wikipedia.org/wiki/Furstenberg%27s_proof_of_the_infinitude_of_primes

Apart from that there are almost infinitely many proofs..

$\endgroup$
3
  • $\begingroup$ Could you explain the topological proof? I find the Wiki article difficult to parse... $\endgroup$
    – user45572
    Jun 13, 2014 at 22:06
  • $\begingroup$ @user45572 Explanation: Declare each arithmetic sequence to be "closed", and extend this terminology to finite unions. Verify that the complement of a finite set is not closed. Verify that the complement of $\{\pm 1\}$ is the union of arithmetic sequences whose ratios are exactly the prime numbers (by prime factorization). Since it's cofinite, this must be an infinite union, QED. $\endgroup$
    – Ryan Reich
    Jun 13, 2014 at 22:18
  • $\begingroup$ Note that it's not really a topological proof at all. $\endgroup$
    – Ryan Reich
    Jun 13, 2014 at 22:23
1
$\begingroup$

I like Dirichlet's theorem on primes in arithmetic progressions. Shows not only infinitely many primes, but infinitely many primes in each (nontrivial) residue class in any modulus. Proof relies on analytic properties of Dirichlet series.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.