(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.1 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.2 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.3
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,4 but the following seems cleaner to us.
Let be the number of primes up to . To get a count (lower estimate) for , write any number up to r in the form
where b is “square-free”. So, for example, 756 = 36 x 21 would be written as 62 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
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 primes to choose or not, that shows
Together the choices for a and b must capture all numbers up to r, and so
Dividing by , we have
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 be a prime, and let be some prime factor of . Then so , and thus .
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.