122
$\begingroup$

This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show you what proofs I have and I'd like to know more because I think it's cool to see that something can be proved in so many different ways.

Proof 1 : Euclid's. If there are finitely many primes then $p_1 p_2 ... p_n + 1$ is coprime to all of these guys. This is the basic idea in most proofs : generate a number coprime to all previous primes.

Proof 2 : Consider the sequence $a_n = 2^{2^n} + 1$. We have that $$ 2^{2^n}-1 = (2^{2^1} - 1) \prod_{m=1}^{n-1} (2^{2^m}+1), $$ so that for $m < n$, $(2^{2^m} + 1, 2^{2^n} + 1) \, | \, (2^{2^n}-1, 2^{2^n} +1) = 1$. Since we have an infinite sequence of numbers coprime in pairs, at least one prime number must divide each one of them and they are all distinct primes, thus giving an infinity of them.

Proof 3 : (Note : I particularly like this one.) Define a topology on $\mathbb Z$ in the following way : a set $\mathscr N$ of integers is said to be open if for every $n \in \mathscr N$ there is an arithmetic progression $\mathscr A$ such that $n \in \mathscr A \subseteq \mathscr N$. This can easily be proven to define a topology on $\mathbb Z$. Note that under this topology arithmetic progressions are open and closed. Supposing there are finitely many primes, notice that this means that the set $$ \mathscr U \,\,\,\, \overset{def}{=} \,\,\, \bigcup_{p} \,\, p \mathbb Z $$ should be open and closed, but by the fundamental theorem of arithmetic, its complement in $\mathbb Z$ is the set $\{ -1, 1 \}$, which is not open, thus giving a contradiction.

Proof 4 : Let $a,b$ be coprime integers and $c > 0$. There exists $x$ such that $(a+bx, c) = 1$. To see this, choose $x$ such that $a+bx \not\equiv 0 \, \mathrm{mod}$ $p_i$ for all primes $p_i$ dividing $c$. If $a \equiv 0 \, \mathrm{mod}$ $p_i$, since $a$ and $b$ are coprime, $b$ has an inverse mod $p_i$, call it $\overline{b}$. Choosing $x \equiv \overline{b} \, \mathrm{mod}$ $p_i$, you are done. If $a \not\equiv 0 \, \mathrm{mod}$ $p_i$, then choosing $x \equiv 0 \, \mathrm{mod}$ $p_i$ works fine. Find $x$ using the Chinese Remainder Theorem.

Now assuming there are finitely many primes, let $c$ be the product of all of them. Our construction generates an integer coprime to $c$, giving a contradiction to the fundamental theorem of arithmetic.

Proof 5 : Dirichlet's theorem on arithmetic progressions (just so that you not bring it up as an example...)

Do you have any other nice proofs?

$\endgroup$
7
  • 7
    $\begingroup$ This should be community wiki. Anyway, here's one: the harmonic series diverges, so by considering the Euler product, there must be infinitely many primes. A bit of a sledgehammer though... $\endgroup$
    – Zhen Lin
    Jul 7, 2011 at 4:41
  • 11
    $\begingroup$ Chapter 1 of Aigner-Ziegler, Proofs from THE BOOK contains six proofs (most of them were already mentioned, though). $\endgroup$
    – t.b.
    Jul 7, 2011 at 5:02
  • 11
    $\begingroup$ @Patrick: it is strange that, having asked for proofS, you accepted one answer... $\endgroup$ Jul 7, 2011 at 5:09
  • 2
    $\begingroup$ I just want to note here, that Euclid's proof was in fact both direct and constructive. $\endgroup$ Jul 7, 2011 at 5:19
  • 5
    $\begingroup$ Euclid's proof is misrepresented here, as it is by many illustrious authors. Euclid never assumed there are only finitely many; his proof was not by contradiction Catherine Woodgold and I published a paper about this misunderstanding: "Prime Simplicity", Mathematical Intelligencer, Volume 31, Number 4, 44-52, DOI: 10.1007/s00283-009-9064-8 $\endgroup$ Nov 17, 2011 at 1:13

27 Answers 27

62
$\begingroup$

The following proof is morally due to Euler. We have

$$\prod_{p \text{ prime}} \left( \frac{1}{1 - \frac{1}{p^2}} \right) = \zeta(2) = \frac{\pi^2}{6}.$$

The RHS is irrational, so the LHS must have infinitely many factors.

$\endgroup$
5
  • 11
    $\begingroup$ One can write down the same proof with Apéry's theorem and $\zeta(3)$, but that is really overkill... $\endgroup$ Jul 7, 2011 at 5:17
  • 4
    $\begingroup$ I wonder what the fact that $\frac{\pi^2}{6}$ is transcendental tells us about the distribution of prime numbers. $\endgroup$ Jun 7, 2013 at 3:13
  • $\begingroup$ But the formula is derived after knowing there are infinite primes right? So this proof is circular. $\endgroup$
    – N.S.JOHN
    Apr 28, 2016 at 3:07
  • $\begingroup$ @N.S.JOHN: no, you don't need to know anything about how many primes there are to prove this formula. $\endgroup$ Apr 28, 2016 at 3:08
  • $\begingroup$ Alright then .. $\endgroup$
    – N.S.JOHN
    Apr 28, 2016 at 3:10
35
$\begingroup$

When I taught undergraduate number theory I subjected my students to a barrage of proofs of the infinitude of the prime numbers: see these lecture notes. I gave eight proofs altogether. Of course by now the list which has been currently compiled has a large overlap with mine, but one proof which has not yet been mentioned is Washington's algebraic number theory proof:

Proposition: Let $R$ be a Dedekind domain with fraction field $K$. If $R$ has only finitely many prime ideals, then for every finite degree field extension $L/K$, the integral closure $S$ of $R$ in $L$ is a PID.

(The proof boils down to two facts: (i) a Dedekind domain with finitely many prime ideals is a PID. (ii) with notation as above, the map $\operatorname{Spec S} \rightarrow \operatorname{Spec R}$ is surjective and at most $[L:K]$-to-one, so $R$ has infinitely many prime ideals iff $S$ has infinitely many prime ideals.)

Corollary: There are infinitely many primes.

Proof: Applying the Proposition with $R = \mathbb{Z}$, if there were only finitely many primes, then for every number field $K$, the ring $\mathbb{Z}_K$ of integers in $K$ would be a PID, hence a UFD. But for instance this fails for $K = \mathbb{Q}(\sqrt{-5})$, as $2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ is a nonunique factorization into ireducible elements (since there are no elements of norm $2$ or $3$) in $\mathbb{Z}_K = \mathbb{Z}[\sqrt{-5}]$.

$\endgroup$
3
  • $\begingroup$ I must admit I don't know anything about algebraic number theory to understand your argument, but I'll be taking a course this year about that so I guess I'll read it later on. =) +1 $\endgroup$ Jul 7, 2011 at 20:17
  • 2
    $\begingroup$ By the way, maybe I should say that I didn't give all eight proofs in my lectures (or maybe I shouldn't, so that people will think that I cover everything in my classes that appears in my lecture notes: that would be pretty impressive). This proof I either skip entirely or summarize as "Actually, it is possible to deduce the infinitude of the prime numbers directly from the lack of unique factorization in $\mathbb{Z}[\sqrt{-5}]$, but this requires methods from more advanced number theory." $\endgroup$ Jul 7, 2011 at 20:40
  • $\begingroup$ @Pete L. Clark : Now that I understand your proof, I am amazed by the fact that $5$ actually allows you to finish this argument! I know there are other examples, but in the other proofs we never had to consider any particular prime, which is the case in this proof, because "you need" a counter example. This seems to be a general techinque to prove that $|\mathrm{Spec} (R)| = \infty$ in other rings than $\mathbb Z$ though... $\endgroup$ Oct 26, 2013 at 1:14
34
$\begingroup$

The following proof is due to Euler. We have

$$\prod_{p \text{ prime}, p \le m} \left( \frac{1}{1 - \frac{1}{p}} \right) \ge \sum_{n=1}^m \frac{1}{n}.$$

The RHS diverges as $m \to \infty$, so the LHS must have an unbounded number of factors.

$\endgroup$
2
  • $\begingroup$ Didn't think of the ones with Euler products, I never came across those. Thanks for both proofs! $\endgroup$ Jul 7, 2011 at 5:00
  • $\begingroup$ @Patrick: well, this is just a simplified version of an argument about the zeta function, and such arguments are of course the heart of the proof of Dirichlet's theorem. $\endgroup$ Jul 7, 2011 at 5:11
22
$\begingroup$

Let $p_1,...,p_n$ be the primes less or equal $N$. Any integer less or equal $N$ can be written as $p_1^{e_1}\cdot...\cdot p_n^{e_n}\cdot m^2$ with $e_i\in\{0,1\}$ and $m\leq\sqrt{N}$. So there are at most $2^n\sqrt{N}$ integers less or equal $N$, i.e. $N\leq2^n\sqrt{N}$. Simplifying and taking logarithms gives $(1/2)\log N\leq n\log2$. Since $N$ is unbounded, so is $n$. (Due to Erdős, taken from the book Gamma by Julian Havil, a book on Euler's constant.)

$\endgroup$
4
  • 1
    $\begingroup$ I don't remember seeing this proof. I like it a lot. $\endgroup$ Jul 7, 2011 at 17:18
  • 1
    $\begingroup$ Yes, it's quite nice. It can be extracted from the sixth proof in Proofs from the Book, which is also attributed to Erdős. It is a stronger version of the counting proof I gave and gives a slightly stronger "weak PNT." $\endgroup$ Jul 7, 2011 at 18:50
  • 4
    $\begingroup$ I like the following slight rephrasing. Suppose the number of primes is finite, say $C$. Every $n\in\{1,\ldots,N\}$ can be written uniquely in the form $k^2\ell$ where $\ell$ is a product of distinct primes. The number of choices for $k$ is at most $\sqrt{N}$, and the number of choices for $\ell$ is at most $2^C$. Therefore the number of integers in $\{1,\ldots,N\}$ is at most $2^C\sqrt{N}$, which clearly cannot remain true as $N$ increases. $\endgroup$
    – idmercer
    Jul 8, 2011 at 0:44
  • $\begingroup$ I prefer his phrasing, no offense. $\endgroup$ Jul 9, 2011 at 22:16
16
$\begingroup$

Proof 3 is due to Fürstenberg (see also the Wikipedia page) and is honestly not that different from Euclid's proof. See this MO question and the corresponding links for an extended discussion.

I give a counting proof here that I think should be better-known. Briefly, let $\pi(n)$ denote the number of primes less than or equal to $n$. The prime factorization of any positive integer less than or equal to $n$ has the form $\prod p_k^{e_k}$ where

$$\sum_{k=1}^{\pi(n)} e_k \log p_k \le \log n$$

so it follows that $e_k \le \log_2 n$ for all $k$, hence that $n \le \left( \log_2 n + 1 \right)^{\pi(n)}$. This gives the following extremely weak version of the PNT:

$$\pi(n) \ge \frac{\log n}{\log (\log_2 n + 1)}.$$

One can use the same idea to prove that any strictly increasing sequence of positive integers which is polynomially bounded has the property that infinitely many primes divide one of its terms, which is stronger than what can be achieved using Euclid's proof (which only gets you this result for polynomials).

Edit: According to Pete Clark's notes, the above proof was in some form given by (but does not seem to be originally due to) Chaitin. In his formulation it can be summarized using the following slogan: if there were finitely many primes, then the prime factorization of a number would be too efficient a way of representing it. This is quite a nice slogan in that it immediately suggests the generalization to polynomially bounded sequences.

$\endgroup$
7
  • $\begingroup$ I added two links to Fürstenberg's proof. I hope you don't mind. $\endgroup$
    – t.b.
    Jul 7, 2011 at 4:52
  • $\begingroup$ Whew. Nice. Seriously, reading all those proofs, I remember other proofs. XD Giving you the green check Qiao :) thanks a lot $\endgroup$ Jul 7, 2011 at 5:03
  • 3
    $\begingroup$ @Patrick: don't take this the wrong way, but I don't really understand the point of accepting an answer to a big-list question... $\endgroup$ Jul 7, 2011 at 5:11
  • $\begingroup$ It's just a way of giving extra rep. I'm being thankful. You gave me like four proofs. $\endgroup$ Jul 7, 2011 at 5:23
  • 9
    $\begingroup$ @Patrick: I think you will get more answers if you don't accept an answer. More answers accumulating means more people get to learn about interesting proofs, which is much more important than reputation. I'm not sure accepting CW answers gives reputation, and even if it did I don't really need it... $\endgroup$ Jul 7, 2011 at 5:24
11
$\begingroup$

Source : Proofs from the Book, by Martin Aigner and Günter M. Ziegler.


Here is one more proof. I don't really know who discovered it.

Let $\pi(x) = \# \bigl\{ \text{No of primes} \ \leq x \bigr\}$. Suppose $p$ is the largest element. We consider the Mersenne number $2^{p}-1$, and show that for any prime factor $q$ of $2^{p}-1$ is bigger than $p$. So let $p$ be a prime dividing $2^{p}-1$. So we have $2^{p} \equiv 1 \ (\text{mod} \ q)$. Since $p$ is prime, his means that, the element $2$ has order $p$ in the multiplicative group $\mathbb{Z}_{q}\setminus \{0\}$ of the field $\mathbb{Z}_{q}$. This group has $q-1$ elements, so by Lagrange's theorem, we know that the order of every element divides the order of the group. Hence $p \mid (q-1)$, which shows that $p < q$.

$\text{Added.}$

$\endgroup$
18
  • 9
    $\begingroup$ Ugh. Chandru, you have been warned time and time again about citing your sources. This is, nearly word for word, the second proof in Proofs from the Book. $\endgroup$ Jul 7, 2011 at 5:27
  • 11
    $\begingroup$ @chandru: "How am I to remember the fact where I had taken this from." You don't seem to understand that it is your responsibility to remember this, or at least not to reproduce things when you know you have a habit of verbatim copying. This same attitude applied to your written work would get you kicked out of many if not most universities. $\endgroup$ Jul 7, 2011 at 6:40
  • 3
    $\begingroup$ Here is the source. As Qiaochu said, it is almost verbatim copying. $\endgroup$ Jul 7, 2011 at 6:55
  • 6
    $\begingroup$ Saying you don't know to whom the proof is due allows for the possibility that you wrote up the argument yourself. (For instance, a mathematically equivalent version of this same proof appears in the document linked to in my answer, but the argument has been rewritten in my own words.) Even to say "I took this almost verbatim from somewhere, but I can't remember where" is not a good practice, because you took the time to copy something without taking the care to record what you were copying. If others can catch you out, then with the same amount of effort you can retrieve your sources. $\endgroup$ Jul 7, 2011 at 7:39
  • 3
    $\begingroup$ @Chandru: the post is much better now. Thank you for taking our concerns seriously. $\endgroup$ Jul 9, 2011 at 15:20
10
$\begingroup$

Another well-known proof which is somewhat related to two of the proofs by Qiaochu above is to note that for every prime $p \leq n$, the power of $p$ dividing $n!$ is at most $p^{\frac{n-1}{p-1}}$. Since certainly $p^{\frac{1}{p-1}} \leq 2$, we obtain that $2^{n \pi(n)} > n!$, where $\pi(n)$ is the number of primes less than or equal to $n$. Using Stirling's formula shows that $\pi(n) \to \infty$ as $n \to \infty$. A more careful version of this argument goes back to Chebyshev.

In an AMM paper (around 1954) called "A Method for finding primes", John Thompson came up with a simple, but very nice, variant of Euclid's argument: if we list a set of distinct primes, $\{p_1,p_2,\ldots, p_n\}$, not necessarily in increasing order, then for any $k \leq n$, the integer $p_1 \ldots p_k - p_{k+1}\ldots p_n$ is not divisible by any of the given $p_i$. This may be $\pm 1$, of course, but in that case you can interchange various $p_i$'s. The point is that you get lots more primes not in your original list this way, and they are divisors of numbers not necessarily so much larger than the primes you start with.

$\endgroup$
4
  • 5
    $\begingroup$ You don't need the full strength of Stirling's formula; using the fact that $e^x \ge \frac{x^n}{n!}$ for $x \ge 0$ we get $e^n \ge \frac{n^n}{n!}$ or $n! \ge \left( \frac{n}{e} \right)^n$. I learned this argument from Terence Tao's very nice post here: terrytao.wordpress.com/2010/01/02/… $\endgroup$ Jul 7, 2011 at 13:16
  • $\begingroup$ Yes. Nice simplification, thanks. $\endgroup$ Jul 7, 2011 at 13:50
  • $\begingroup$ I did not know this proof earlier. Recently I was playing around with some of the above estimates and got the same result. I was overjoyed thinking that I found a new proof, and I just came here to see if someone had already mentioned this proof. $\endgroup$ Jul 5, 2021 at 17:15
  • 1
    $\begingroup$ @S.SundaraNarasimhan : That is a common experience for Mathematicians, part of being in the profession. $\endgroup$ Jul 5, 2021 at 19:16
8
$\begingroup$

One proof approach is to construct an infinite set of numbers, any two of which are relatively prime. The proof using Fermat numbers/Euclid's proof can be considered to follow that approach (so I am not sure if I should even be adding this answer!).

We construct a set explicitly as follows.

Start with $3$. Now if we already have $\{x_1, x_2, \dots, x_n\}$ so far, whose prime divisors are $\{p_1, p_2, \dots, p_r\}$, take $x_{n+1} = 2^{(p_1 -1)(p_2 - 1) \dots (p_r - 1)} + 1$

By Fermat's little theorem, $x_{n+1} = 1 \mod p_i$ and thus is relative prime to each $x_i$.

Incidentally the Fermat numbers are relative co-prime can also be proved as follows:

If $x = 2^{2^m}$ and $2^{2^m} + 1 = 0 \mod p$, (i.e. $x = -1 \mod p$) then since $2^{2^{n}}$ is an even power of $x$, we have that $2^{2^n} + 1 = 2 \mod p$.

$\endgroup$
1
  • $\begingroup$ This is the idea behind the two proofs in my question ; the one with the sequence $2^{2^n}+1$ and the other one with the Chinese Remainder Theorem. But the approach with your $x_{n+1}$ I didn't know, thanks. $\endgroup$ Jul 7, 2011 at 20:14
8
$\begingroup$

The following proof can be extracted from Erdős' proof of Bertrand's postulate (although perhaps this argument should be credited to Chebyshev). We need the following two lemmas from that page.

Lemma 1: ${2n \choose n} > \frac{4^n}{2n+1}$.

Lemma 2: The greatest power $R(p, n)$ of a prime $p$ dividing ${2n \choose n}$ satisfies $p^{R(p, n)} \le 2n$.

From these two lemmas it follows that

$$\frac{4^n}{2n+1} < {2n \choose n} \le (2n)^{\pi(2n)}$$

which is a contradiction for large $n$ if $\pi(2n)$ is bounded. This gets us within a constant of the PNT:

$$\pi(2n) \ge \frac{n \log 4 - \log (2n+1)}{\log 2n}.$$

$\endgroup$
7
$\begingroup$

Here's a proof in the language of ring theory. By the division algorithm, $\mathbb{Z}$ is a principal ideal domain. Thus its maximal ideals are precisely those nonzero of the form $(p)$ where $p$ is prime.

Assume for contradiction that there are finitely many primes $p_1, \dots, p_n$. Then the product $j = p_1 \cdots p_n$ lies in every maximal ideal of $\mathbb{Z}$, hence in its Jacobson radical. It follows that $1 + j$ is a unit in $\mathbb{Z}$. But this is absurd, not least because $1 + j > 1$.

(While poking around to see if the proof had already appeared on this site, I also stumbled on a very nice result by Bill Dubuque that an infinite ring with "fewer units than elements" has infinitely many maximal ideals. Apparently, this strengthens an argument by Kaplansky.)

$\endgroup$
1
  • $\begingroup$ But I think that if you reformulate the actual arguments by translating all the ''language'' you use, this is Euclid's proof. Doesn't mean I don't like the translation though! $\endgroup$ Jan 25, 2014 at 0:10
7
$\begingroup$

There's a collection at https://primes.utm.edu/notes/proofs/infinite/ (Proofs that there are infinitely many primes)

$\endgroup$
1
  • $\begingroup$ Actually four of the five proofs there are in my question, but I like the fifth one! $\endgroup$ Jul 7, 2011 at 5:00
6
$\begingroup$

There is a very clever one-line proof which I can't understand why it's not here. The Proof:

$$ 0 < \prod\limits_{p} \sin\left(\frac{\pi}{p}\right) = \prod\limits_{p} \sin\left(\frac{\pi(1+2\prod_{p'}p')}{p}\right) =0 . $$

This proof has created by Sam Northshield in 2015 and published in American Mathematical Monthly.

$\endgroup$
5
  • $\begingroup$ The inequality is because you are taking a product of positive numbers. The first equality is because the product of all $p'$ is divisible by $p$, so the argument is congruent to $\pi/p$ modulo $2\pi$. The last equality is because the integer $1+2 \prod$ is divisible by some prime, hence the factor corresponding to it vanishes. I remember seeing this proof, it's a nice one! $\endgroup$ Feb 13, 2017 at 19:55
  • $\begingroup$ I don't see how you can prove that (1+2∏p')/p is an integer. The p in the denominator isn't "any" p. It's each and every p. $\endgroup$
    – Aheho
    Mar 15, 2017 at 4:21
  • $\begingroup$ Neat, but again this is just Euclid. $\endgroup$
    – ocg
    Oct 9, 2017 at 22:35
  • $\begingroup$ @Aheho probably one p is enough to get a zero? $\endgroup$
    – runr
    Sep 20, 2018 at 11:55
  • $\begingroup$ @Aheho: I am late, but we are not trying to prove that $(1+2\prod p^{\prime})/p$ is an integer. We are trying to prove that, for each $p,$ $(2\prod p^{\prime})/p$ is an integer, which it clearly is, since $p$ appears as one of the $p^{\prime}$ in the product. This is enough to establish the first equality. The fact that $1+2\prod p^{\prime}$ is divisible by some prime is totally unrelated, it's just pure number theory. The entire computation takes place in the context "Assume there are only finitely many primes; now we take the products over all of them." $\endgroup$
    – Will R
    Jan 27, 2019 at 5:46
5
$\begingroup$

Let $P$ be a polynomial with integer coefficients $a_d$ and degree $n$. Then $$ I(P) = \int_{0}^{1} P(x) dx = \sum_{k = 0}^{n} \frac{a_k}{k + 1} $$ If $I(P) \neq 0$ then multiplying by $L = \text{lcm}[1,2,\ldots, n+1]$ we get $$ L \cdot |I(P)| \geq 1 $$ because $L \cdot I(P)$ is an integer. Now note that $$ L = \exp(\psi(n+1)) $$ where $\psi(n) = \sum_{p^{k} \leq n} \log p$. Therefore $$ \exp(\psi(n+1)) \geq \frac{1}{|I(P)|} $$ Choose $P(x) = x^m ( 1 - x)^m$. Then on $0 < x < 1$ we have $|P(x)| \leq 2^{-2m}$. Therefore $|I(P)| \leq 2^{-2m}$. Therefore $$ \psi(2m+1) \geq 2m \log 2 $$ This proves the infinitude of the primes. In fact it proves more, it proves the Chebychev bound $$ \pi(x) \gg x / \log x $$ This proof cannot be refined to a proof of the prime number theorem. The optimal choice of the polynomial gives only a constant of $0.86 \ldots$ in place of $\log 2$.

REFERENCES: Chapter 10 of Montgomery's book "Ten lectures on the interface between harmonic analysis and analytic number theory".

EDIT: Here are the details of the $\gg$ bound. Note that $\psi(2m + 1) \geq 2m \log 2$ implies $\psi(x) \gg x$ for all $x$. The prime squares and higher contribute $O(\sqrt{x} \log x)$ to $\psi(x)$ and the primes $p$ contributes at most $\pi(x) \log x$ since each $\log p \leq \log x$. Therefore $$ \pi(x) \log x + \sqrt{x}\log x \gg \psi(x) \gg x $$ Hence $$ \pi(x) \gg x / \log x $$

$\endgroup$
5
  • $\begingroup$ I don't see how this proves the lessthan-lessthan bound. Can you explain in more detail? I'm interested. $\endgroup$ Jun 30, 2013 at 0:46
  • $\begingroup$ Yes of course! It's a rather standard derivation but I'll include it in the edits. $\endgroup$
    – blabler
    Jun 30, 2013 at 1:54
  • $\begingroup$ At least to me this proof has a touch of transcendental number theory: First, the use of the fact that a non-zero integer has to be in absolute value $\geq 1$. Secondly, the optimization problem involving a choice of a polynomial with integer coefficients. $\endgroup$
    – blabler
    Jun 30, 2013 at 2:12
  • $\begingroup$ Am I supposed to read the reference to understand the proof better? Because right now I don't get it. Maybe it feels trivial to you but it's not to me. $\endgroup$ Jun 30, 2013 at 3:00
  • $\begingroup$ Thanks for fixing the details. Took me a while to understand that $\psi(n)$ function actually! I didn't read it well enough the first time. $\endgroup$ Jun 30, 2013 at 3:08
5
$\begingroup$

This is taken from Section 1.4 of Andrew Granville's notes on Prime numbers:

We finish this section by proving that for any $f(t) \in \mathbb Z[t]$ of degree $\ge1$ there are infinitely many distinct primes $p$ for which $p$ divides $f(n)$ for some integer $n$. We may assume that $f(n) \ne 0$ for all $n \in \mathbb Z$ else we are done. Now suppose that $p_1,\ldots,p_k$ are the only primes which divide values of $f$ and let $m = p_1 \cdots p_k$. Then $f(nmf(0)) \equiv f(0) \pmod{mf(0)}$ for every integer $n$, by exercise 1.2a.a, so that $f(nmf(0))/f(0) \equiv 1 \pmod m$. Therefore $f(nmf(0))$ has prime divisors other than those dividing $m$ for all $n$ but the finitely many $n$ which are roots of $(f(tmf(0)) - f(0))(f(tmf(0)) + f(0))$, a contradiction.

Exercise 1.2a.a is: Prove that if $f(t) \in \mathbb Z[t]$ and $r,s\in\mathbb Z$ then $r-s$ divides $f(r)-f(s)$.

Other parts of his course notes might be interesting in connection with this question, too.

$\endgroup$
1
  • 1
    $\begingroup$ Funny you should say that, Andrew's my advisor. XD Thanks! $\endgroup$ Nov 27, 2011 at 18:19
4
$\begingroup$

Prove infinite number of primes using Wilson's Theorem and Euclid's argument:

Let $P$ be the maximum prime number. From Wilson's Theorem, $P$ is prime if and only if $P \mid (P - 1)! + 1$. Thus, $(P - 1)! + 1 = kP$, for some natural number $k$.

Let $n > P$ since there are infinite natural numbers,

$(n - 1)! + 1 = rs$, for some natural numbers $r$ & $s$.

If $r=n$ or $s=n$, then $n$ is prime (Wilson's Theorem) & $n > P$ (proven).

If both $r$ and $s$ are not equal to $n$, let $r$ represents one of the prime factor of $(n - 1)! + 1$.

$r$ cannot be $2$ to $(n-1)$, otherwise $r \mid (n - 1)!$ and $r \mid [(n - 1)! + 1]$ at the same time then $r \mid 1 \rightarrow \; r = 1$, which is impossible.

So this prime factor $r$ is not from $2$ to $n$; it is another prime $> n > P$.

Leow (2013)

$\endgroup$
4
$\begingroup$

Proofs from the book has already been mentioned so it seems silly to spell out yet another proof from that source, but on the other hand I feel that this proof deserves special mentioning since it has two rather striking properties:

1) Like you mention in your post the point of many proofs is the construction of a sequence of numbers in which each member $a_n$ is coprime to each of the (finitely many) previous ones. A special feature of this proof is that it shows this fact (for a special sequence $a_1, a_2, a_3, \ldots$) by showing that $a_n$ is comprime to all the (infinitely) $a_m$ succeeding it. The fact that both properties of $a_n$ are equivalent is of course completely elementary but still I found it initially hard to get my head around. And intuitively it is of course weird that it is easier to prove a number coprime to an infinite set of numbers (its successors) than to a finite set of numbers (it predecessors).

2) The proof relies on a mathematical fact that is very dear to me (and probably many mathematicians) as it was the first truly beautiful formula I discovered myself: $$2+2 = 2*2$$ Of course, being older and wiser, this looks like a 'strong law of small numbers'-type phenomenon rather than a deep equation, so i was all the more happy to see it used as the fundament of a proof of one of the most celebrated facts of mathematics.

So here goes the proof:

Start with an odd number $a_1$ and construct an infinite sequence of odd numbers by $$a_{n+1} = a_n^2 - 2$$

To see that $a_n$ has no common divisors with its successors let $q$ be a prime divisor of $a_n$. It suffices to show that no $a_m$ is never congruent $0 \mod q$ for $m >n$. Well, $a_{n+1} \equiv -2 \mod q$ and, courtesy of the above mentioned beautiful formula, $a_m \equiv 2 \mod q$ for every $m \geq n+2$. $q$ being odd this proves the claim.

$\endgroup$
8
  • $\begingroup$ To be honest, I'm not really... impressed. But I'm happy you're amazed. $\endgroup$ Jan 19, 2014 at 0:41
  • $\begingroup$ Well of course after Euclid every proof consisting of constructing an infinite sequence of mutually coprime integers is a bit derivative. What would be truly impressive is to have a proof that does not rely on the fact that every sufficiently large number is divisible by at least one prime, but I don't think such a proof can exist. $\endgroup$
    – Vincent
    Jan 19, 2014 at 12:59
  • $\begingroup$ Um... Every number not in $\{-1,0,1\}$ is divisible by at least one prime. If by sufficiently large you mean $\ge 2$ that's a fancy way to say it. Otherwise, the topological proof ultimately does that ; it only secretly uses the fundamental theorem of arithmetic, but not in a very deep way. It is definitely my favorite. $\endgroup$ Jan 19, 2014 at 14:14
  • $\begingroup$ Ha, I meant $\geq 2$ but wrote it in a fancy way pretty much because of the topological proof: until I read your comment I believed the topological proof ultimately used that the set of numbers not divisible by any prime is finite (rather than being just $\{-1, 1\}$ which of course also is true). Now however I realize that (even better) it only needs the set of numbers not divisible by any prime to be not-open in this special topology, which is a much weaker statement. I wonder if there is a non-euclidean ring in which this distinction can be made explicit. Anyway: thank you for this insight! $\endgroup$
    – Vincent
    Jan 19, 2014 at 14:57
  • $\begingroup$ To clarify: what I meant with my last question is 'is there a non-noetharian ring in which the set of elements not divisible by any irreducible element is infinite but not open in the topology generated by cosets of ideals?' If I understand things correctly in such a ring you could use the topological proof to show the existence of infinitely many irreducibles. (Or should I replace irreducibles with primes here to make the proof go through?) Anyway, infinite sequences of coprime elements seem to be quite useless in such a ring... $\endgroup$
    – Vincent
    Jan 19, 2014 at 15:14
4
$\begingroup$

Here is another idea to prove this statement. Our instructor attributed it to the French mathematician Hermite. The proof goes as follows:

for a given integer $n$. Let $q_n$ be the greatest prime factor of $n! +1$. We claim that $q_n > n$. If not so, then clearly $q_n \mid n! $ and by construction $q_n\mid(n! + 1)$, consequently $q_n\mid1$. Which is impossible, a contradiction reached. Thereby, always there exists a prime number $q_n$ greater than $n$ for any integer $n$ as required.

$\endgroup$
2
$\begingroup$

One can prove directly that the Sieve of Eratosthenes produces an infinite sequence of primes (and produces every prime). This is a worthwhile proof to record since, while it lacks much novel content, it is reassuring that the first method one learns to find primes actually works and that one may prove its correctness without any terribly clever tricks - not even appealing to the fact that every number has a prime divisor. This proof also has the advantage of being constructive.


We define, recursively, an ascending sequence of positive integers $p_1,p_2,p_3,\ldots$ by the following rule: to determine $p_n$, form the set $S_n$ of natural numbers greater than $1$ not divided by any previous term of the sequence; formally, this set is: $$S_n=\{k\in\mathbb N: k>1\text{ and for all }n' < n\text{ we have }p_{n'} \text{ does not divide } k\}$$ Let $p_n=\min S_n$.

Claim 1: This sequence is well-defined.

The only obstacle here is to see that every $S_n$ actually has a minimum since, aside from this possible issue of non-existence, this is a perfectly good recursive definition. Since $S_n$ is a set of natural numbers, is the same as showing that it is non-empty. We can use the main idea of Euclid's proof here and note that $1+\prod_{n'<n}p_{n'}$ is in $S_n$ to see this (or exhibit an element of $S_n$ in any other of the numerous ways one might).

Claim 2: Every term in this sequence is prime.

To prove this, suppose that $p_n=xy$ for some $n\in \mathbb N$ and some $x,y\in \mathbb N$ both greater than $1$. Note that $x<p_n$, which implies that $x\not\in S_n$ by the minimality of $p_n$ in $S_n$. Therefore, there must be some $n'<n$ such that $p_{n'}$ divides $x$. Then $p_{n'}$ would also divide $p_n$, contradicting that $p_n\in S_n$.

Claim 3: This sequence is strictly increasing.

Note that $S_{n+1}$ is a subset of $S_n$, since the condition for inclusion is more strict. Therefore, $p_n$ is a lower bound for $S_{n+1}$ and since $p_n$ cannot be in $S_{n+1}$ by definition, it is a strict lower bound. Thus $p_n < p_{n+1}$ since $p_{n+1}\in S_{n+1}$.

Combined, these three claims show that $p_1,p_2,p_3,\ldots$ is an enumeration of infinitely many distinct prime numbers.


Since we're so close to it, one might as well show one more thing, even if it's not strictly needed:

Bonus claim: Every prime is in this sequence.

For this, let $q$ be a prime and let $n$ be the smallest natural number so that $p_n \geq q$. We claim that $p_n=q$. Note that $q$ must be in $S_n$ because it has no divisors $d$ with $1<d<q$ - in particular, no $p_{n'}$ with $n'<n$ can divide it. Minimality of $p_n$ therefore gives $p_n \leq q$ - but, our choice of $n$ then gives $p_n=q$ by antisymmetry.

$\endgroup$
2
$\begingroup$

Here is a proof which essentially is in the same spirit as that of Euclid, but I have not seen this written up somewhere. So I mention it here.

Let $p_1,p_2,\ldots p_n$ be the only prime numbers. Then consider the number $$s=p_2p_3\cdots p_n+p_1p_3\cdots p_n+ \ldots + p_1p_2\ldots p_{n-1}.$$ Then $p_i$ does not divide $s$ for $1\leq i\leq n$.

Thus the number $s$ has a new prime factor other than $p_i$, contradicting our assumption that $p_i$ are the only primes.

$\endgroup$
2
$\begingroup$

There is an older post from 2011 that you should check out: Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?.

Also you should have a look at a proof (attributed to Filip Saidak) that runs as follows:

Let $n \gt 1$ be a positive integer. Since $n$ and $n+1$ are consecutive integers, they must be coprime, and hence the number $n_2 = n(n + 1)$ must have at least two different prime factors. Similarly, the integers $n(n+1)$ and $n(n+1)+1$ are consecutive, therefore coprime, hence the number $n_3 = n(n + 1)(n(n + 1) + 1)$ must have at least three different prime factors. Now continue this process indefinitely.

$\endgroup$
1
$\begingroup$

Let $p$ be the last prime. Then according to Bertrand's postulate the interval $(p,2p)$ contains a prime number. We get a contradiction.

$\endgroup$
1
$\begingroup$

(Another take on Euler's proof, I believe)

Assume there are finitely many primes $\left \{ p_{0}, p_{1}, ... p_{k} \right \}$. Since every natural number admits a unique prime factorization up to reordering:

$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+... = \sum_{n_{0}=0}^{\infty}p_{0}^{-n_{0}}\left ( \sum_{n_{1}=0}^{\infty}p_{1}^{-n_{1}}\left ( \sum_{n_{2}=0}^{\infty}p_{2}^{-n_{2}}\left ( ... \left ( \sum_{n_{k}=0}^{\infty}p_{k}^{-n_{k}} \right ) ...\right ) \right ) \right )$$

$$=\frac{p_{0}}{p_{0}-1}\frac{p_{1}}{p_{1}-1}\frac{p_{2}}{p_{2}-1}...\frac{p_{k}}{p_{k}-1}$$

(The repeated sum accounts for every product of primes exactly once (and includes the number 1). The product below it follows from the geometric series summation formula.)

The R.H.S. converges as there are only finitely many primes, but the L.H.S. is known to diverge. Contradiction.

$\endgroup$
1
$\begingroup$

Maybe you wanna use the sum of reciprocal prime numbers. The argument for the fact that
the series diverges you may find here in one of Apostol's exercise.

$\endgroup$
0
1
$\begingroup$

Consider Euler's totient function applied to primorials. Assume there is a greatest prime number $p_n$, with the associated primorial $p_n\#$ (that is, the product of all $n$ prime numbers).

The totient of $p_n\#$ (call it $k$) is $k=\phi (p_n\#)=\prod_{i=1}^n (p_i-1)$. Since the only number smaller than $p_n$ that is not coprime to at least one of the $p_i$ is $1$, that means there are $k-1$ numbers larger than $p_n$ and smaller than $p_n\#$ that are coprime to every prime number in the assumed "complete list" of $n$ primes.

These $k-1$ numbers must be either prime numbers or products of prime numbers that are not in the list of $n$ primes, and hence are larger than $p_n$. If we identify the new primes in this range and call the largest $p_m$, the argument repeats without limit, proving infinitely many prime numbers.

Some illustrative examples: $p_3\#=2\cdot 3\cdot 5=30$, and $\phi (30)=8$, meaning there are $7$ numbers between $5$ and $30$ that are coprime to $30$. They are $7,11,13,17,19,23,29$, and they all happen to be prime.

$p_4\#=2\cdot 3\cdot 5\cdot 7=210$, and $\phi (210)=48$, meaning there are $47$ numbers between $7$ and $210$ that are coprime to $210$. These include $42$ primes larger than $7$ and the five composites $121, 143, 169, 187, 209$.

$\endgroup$
0
$\begingroup$

Let $P$ be your currently known primes (or more precisely, currently known coprime integers).

Find an $n$ such that $n+P_i$ is not divisible by $P_i$ for each $P_i \in P$. In other words, find a derangement of the original primes.

For example, if $P=\{2,3,7\}$, then you might use $n=5$, where $n+P=\{7, 8, 12\}$, where $2 \nmid 7 \land 3 \nmid 8 \land 7 \nmid 12$. And since $P_i \nmid (n+P_i) \iff P_i \nmid n$, it means $n$ is coprime to all $P_i$ and can be added to $P$.

Repeat as desired; derangements are plentiful and there will be increasingly many in a full permutation of $\prod P$.

$\endgroup$
-1
$\begingroup$

The following proof use the Euler's totient function and relies on the fact that $\phi(m) > 1$ for all $m \geq 3$.

Assume that there are only a finite number of primes say $p_1,p_2,\ldots,p_k$. Look at the product of these finite primes i.e. $$m = p_1 p_2 \cdots p_k$$ Now consider any number $n > 1$. Since there are only finite primes, one of the $p_j$'s must divide $n$. Hence, $\gcd(m,n) > 1$. Hence, $\phi(m) = 1$ contradicting the fact that $\phi(m) > 1$ for all $m \geq 3$.

$\endgroup$
1
  • 1
    $\begingroup$ How to prove that $\varphi(m)>1$ for all $m\geq 3$? For 1 and m-1 are the totative of m?However I need Bezout equation to prove m-1 and m are coprime . $\endgroup$
    – yibotg
    Dec 26, 2014 at 12:39
-3
$\begingroup$

How about this? Let x be a rational in (0,1). Then x is of the form x = m/M with M>m. If x has a non terminating decimal expansion then x must be of the form x = m/p where p is a prime number. Also, the period of x, say T(x), is less than p. Let A = { x such that x is rational in (0,1) and has non terminating decimal expansion } Let B = { y=T(x) such that x is an element of A } We then have that for every y in B there is at least one prime p and natural m such that y = T(x) = T(m/p) < p Since B is unbounded so is the set of prime numbers

$\endgroup$
2
  • 1
    $\begingroup$ The claim $$x\in\mathbb Q\text{ has a non-terminating decimal part}\implies x=\frac{m}{p}\text{ for some prime }p$$ is false. For instance, $x=\frac{1}{90}$ is a counter-example. $\endgroup$
    – user228113
    Aug 6, 2015 at 19:22
  • 2
    $\begingroup$ But, for instance, $0,0555555555...=\frac{1}{18}$ and $18$ is not prime. I don't think we can write $0,0555555555...$ in the form m/p where p is a prime. $\endgroup$
    – Ramiro
    Aug 6, 2015 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .