Erdős’s (not Thue’s) Proof of the Infinity of Primes

(19/10/22 In a comment below, Bernard has noted the proof should be properly attributed to Paul Erdős, not Thue. Thue’s counting argument is similar in spirit, but not as quick.)

This post has no deeper meaning.¹ Its purpose is just to present a very nice argument, which we gave in our talk last week, and which we feel should be better known.

One of the beautiful theorems that every school student should see is the infinity of primes.² The standard Euclid proof tends to be difficult for students to appreciate, however, since, although the arithmetic is trivial, the argument is typically clouded with the unsettling concepts of infinity and contradiction.³

The following proof by Norwegian mathematician Axel Thue involves counting and a little more arithmetic, but avoids a head-on confrontation with infinity. Instead, Thue provides a direct guarantee of the number of primes up to a certain point. Versions of Thue’s argument can also be found at cut-the-knot and in Hardy and Wright,⁴ but the following seems cleaner to us.

Let $\boldsymbol{\pi(r)}$ be the number of primes up to $\boldsymbol{r}$ . To get a count (lower estimate) for $\boldsymbol{\pi(r)}$ , write any number up to r in the form

$\boldsymbol{a^2b\,,}$

where b is “square-free”. So, for example, 756 = 36 x 21 would be written as 6² x 21, with a = 6 and b = 21.

We now count (find upper estimates) on the number of choices for a and b. Since a is squared, of course we must have

$\boldsymbol{a \leqslant \sqrt{r}\,.}$

For b, note that b is a product of primes up to r, and with no higher powers: each prime is either there or it isn’t. Since there are $\boldsymbol{\pi(r)}$ primes to choose or not, that shows

$\boldsymbol{\text{\bf (choices for $\boldsymbol{b}$)} \leqslant 2^{\pi(r)}\,.}$

Together the choices for a and b must capture all numbers up to r, and so

$\boldsymbol{ r \ \leqslant \ \text{\bf (choices for $\boldsymbol{a}$)} \times \text{\bf (choices for $\boldsymbol{b}$)}\ \leqslant \sqrt{r} \ 2^{\pi(r)}\,.}$

Dividing by $\boldsymbol{\sqrt{r}}$ , we have

$\boldsymbol{ 2^{\pi(r) }\geqslant \sqrt{r}\,.}$

Choose r to be an even power of 2, or take logs if you wish, and however you wish.

1) As if our posts usually do.

2) It is part of the Year 11 Specialist Maths curriculum, but whether students have to comprehend the proof is another question.

3) For us, the simplest and nicest variation of the Euclid argument is a 2-liner, based on the obvious fact that any prime factor of n! + 1 is larger than n. So, however many primes you already have, choose n bigger than them all and then n! + 1 must contain new primes. This “we can always find another prime” phrasing is also more faithful to Euclid.

4) Section 2.6. Hardy and Wright give Thue’s argument in a more general form, which they then also employ in an easy proof that Σ1/p = ∞.

2 Replies to “Erdős’s (not Thue’s) Proof of the Infinity of Primes”

Thanks for sharing! I prepared a document earlier this year on seventeen ways of proving the infinitude of primes; it turns out this argument is attributed to Erdos (e.g. see Theorem 4.1 of https://kconrad.math.uconn.edu/blurbs/ugradnumthy/infinitudeofprimes.pdf).

My favourite proof to run through with students (after introducing modular arithmetic and divisibility, Fermat’s little theorem, orders, etc.) is the following:

Let $p$ be a prime, and let $q$ be some prime factor of $2^p-1$ . Then $2^p\equiv 1\pmod{q}$ so $p\mid q-1$ , and thus $q>p$ .

marty says:

October 19, 2022 at 8:51 am

Damn it! Thanks very much, Bernard. I’ve corrected the post. I’m not sure how I got the idea that Thue gave that proof.

Reply

Related posts:

2 Replies to “Erdős’s (not Thue’s) Proof of the Infinity of Primes”

Leave a Reply Cancel reply