Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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

share|improve this question

marked as duplicate by Steven Stadnicki, draks ..., egreg, Daryl, Behaviour Jun 14 at 0:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
I googled "infinitely many primes" and found this –  user88595 Jun 13 at 22:04
    
$$\pi(x) \sim \operatorname{Li} x \sim \frac{x}{\log x}$$ –  Daniel Fischer Jun 13 at 22:07
    
@BalarkaSen Is that a product over primes? How did the summation turn into that? –  user45572 Jun 13 at 22:08
2  
$$\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. –  Balarka Sen Jun 13 at 22:09
    
@DanielFischer Li? –  user45572 Jun 13 at 22:09

7 Answers 7

up vote 5 down vote accepted

$$\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...

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
I think $2^{2^{n}}-1$ has the same property ( ie, at least $n$ different prime factors). –  Geoff Robinson Jun 13 at 23:02

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.

share|improve this answer
    
(+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. –  Balarka Sen Jun 17 at 9:52

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..

share|improve this answer
    
Could you explain the topological proof? I find the Wiki article difficult to parse... –  user45572 Jun 13 at 22:06
    
@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. –  Ryan Reich Jun 13 at 22:18
    
Note that it's not really a topological proof at all. –  Ryan Reich Jun 13 at 22:23

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.

share|improve this answer

There's a proof using Kolmogorov complexity. It's in section 2 of this nice exposition: http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf

share|improve this answer
3  
You should expand on this answer, making it more self-contained! And, then, since this question is closed, you shuold repost at the indicated duplicate! –  kjetil b halvorsen Jun 14 at 17:25
3  
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Hakim Jun 14 at 17:38

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