Let’s take a look at an unusual proof of the infinity of prime numbers.

Variations on Factorisation

By the Fundamental Theorem of Arithmetic, we can write any number as the product of primes. For example, 45 = 5*3², and 100 = 2²5²

A variation of this is that any number can be written as the product of a square-free number s and a square, r², and this can be done uniquely. A square-free number is one where no perfect square divides it. I will call this the number’s sr² form.

For instance, 12 is not square-free, because 4 divides it. To get 12 into its sr² form we write 12 = 3*(2)² = sr², where s=3, and r=2

This result follows nicely from the Fundamental Theorem of Arithmetic. If we have a number such as 3⁴2⁵7³, we write this as r²s = (3²2²7)²(2*7), where r = (3²2²7), and s = 2*7

Essentially, if the prime p is raised to an odd power, say p⁷, clearly we can write p⁷=p⁶p = (p³)²p. We can repeat this for every prime factor, and collect the terms.

To give one more example, 5145=3*5*7³=sr²=(3*5*7)*(7)².

Proof

Erdos says we should factorise numbers into their sr² forms. We start with a worked example and then do the abstract proof. If you find the purely abstract proof too confusing, then the concrete example includes all the key ideas of the proof, but with actual numbers used so that you can follow more easily.

Worked example

Suppose there are only 4 prime numbers, 2,3,5,7. Let’s take a look at all the numbers less than 10,000. All of these are written in their sr² forms. There are only 100 choices for our value of r. That’s because if r=101, then r²=101²=10201, which is greater than 10,000 and thus cannot be a divisor of a number less than 10,000.

What about the number of choices for our square-free component? Well, let’s take a look. For any prime p we can include it, or not at all. That means there are 16=2⁴ possible ways of building the square-free component: {2}, {3}, {5}, {7}, {2*3}, {2*5}, {2*7}, {3*5}, {3*7}, {5*7}, {2*3*5}, {2*3*7}, {2*5*7}, {3*5*7}, {2*3*5*7}, and {1}.

[1 is squarefree, and 1= 2⁰3⁰5⁰7⁰, which is why it is included]

However, that gives only 16 ways of building the square-free component, s, and 100 ways of building the squared component, r². Overall that gives only 1600 = 16*100 possible numbers we can build. That’s a contradiction, as there are 10,000 numbers we need to build! Thus, we must have been wrong in our assumption that there were only 4 primes.

Our more abstract proof will contain the same ideas, but replace the numbers with variables representing numbers, like N, root(N) (the square root of N), k and so on. The key idea will remain the same:we have a number N and k primes. Given N (say, N=10,000), there are only root(N) choices for the r² component (in our example, root(10,000)=100), and only 2^k (in our example, 2⁴) ways of building the square free component. This results in there being ‘too few’ numbers that we can build in an sr² form compared to the number we know can be built. (in our case, we would only have been able to build 1600 out of the 10,000 numbers). This is a contradiction, and thus our assumption that there were finitely many primes must have been wrong.

Proof

The proof is a bit more abstract, but if you have gone through the worked example, hopefully you can see where the ideas are coming through!

Suppose there are only k prime numbers. Now consider the numbers less than N.

There are only root N ways of building the squared component, r², as (root(N)+1)² > N

However, there are only 2^k ways of building the square free component. (Recall that when we had 4 primes, there were 2⁴ square free numbers we can build: more generally, with k primes, there are 2^k primes we can build).

(Optional). Side note on why we can build 2^k square free numbers from k primes. For each number n we create by multiplying some of these k primes together, we can only include one factor of each prime. If we included p^2 then n wouldn't be square free. For all of the k primes, we can either include it, or not include it. That gives 2*2*...*2 options, or 2^k.

That means, we can only build root(N)*2^k numbers less than or equal to N. However, as we saw in the example, for N large enough this is impossible, as root(N)*2^k < N

Essentially, we have tied the growth of numbers we can build to root(N), and root(N) grows more slowly than N.

We can see this in the graph below. The red line shows the growth of 2^k * root(N), and the green line shows the growth of N. For N suitably large, the red line is underneath the green line. This is a contradiction, as the red line represents the number of distinct numbers we can build, and the green line represents the number of distinct numbers we have to build. Thus, when the red line is below the green line, we reach a contradiction, and our assumption that there were only k primes must have been wrong.

And we are done! Thank you for reading :)

If you have any thoughts or suggestions, please leave them below — I read all the comments! For random maths updates you can follow me on twitter, where I am ethan_the_mathmo.