Goldilocks and The Three Proofs of The Infinitude of The Primes

 A fellow PhD student recently asked me "Have you seen the topological proof that there are infinitely many primes?" and I'm possibly in sparse company being excited by this sentence. It reminded me that I'd seen another insanely overpowered proof that there are infinitely many primes a while ago and so I'd like to present both of these along with Euclid's megaclassic proof.

Paul Erdos, the most published mathematician of all time, though agnostic, referred to god as the Supreme Fascist and believed that he held a book of the perfect proof of every theorem in maths. He would exclaim "This one's from The Book" when he saw a particularly elegant proof and the first of our proofs is undoubtedly one of these.

Suppose, for contradiction, that there are a finite number of primes. I'm going to consider the resulting number when I multiply all these finitely many primes together and add 1. This new number is not divisible by any of the primes. Indeed it leaves remainder 1 when divided by any prime, and so its only factors can be itself and 1, meaning I've generated a new prime. This contradicts the assumption that I could enumerate the finitely many primes. This proof is certainly from the book. But why stop there?

Goldilocks stumbled across that proof and decided it didn't require enough machinery. She tried the next one out for size. 

The Riemann zeta function is a bit of a holy grail in mathematics, its zeros having a million dollar bounty, but we can still treat it with elementary methods. The harmonic series (the subject of the sequel to the ant on the rope post) and the Basel problem are both examples of the Riemann zeta function:

We can generalise the exponent in the sum and define the so-called Riemann zeta function:

There is an intimate link between this sum and the prime numbers. Consider the following method, analogous to the sieve of Eratosthenes. Multiply the sum by 1/2^s:

If we subtract this from the original sum then we remove any denominators with a factor of 2:

Now we multiply by 1/3^s:

And subtracting this removes all denominators with a factor of 3:

If we proceed with each prime then we remove every term in the sum except for 1:

Dividing and using some compact notation gives the prime product formula for the Riemann zeta function:

This is in fact more detail than we needed but I wanted to keep s general to show that this holds for all s. If we evaluate at s=1 then we get the harmonic series which blows up to infinity:

But if the right hand side were a finite product it would have a finite value which would be a contradiction, hence there are infinitely many primes.

Goldilocks felt this was overkill. She tried out the following proof, hoping to strike a nice middle ground. We can define a topology on the integers whereby the open sets are generated by arithmetic sequences:

We can show that in this topology all open sets are closed. If I remove an arithmetic sequence from the integers then I can split what remains into shifted arithmetic sequences with the same common difference:

Taking complements shows that all open sets are also closed. Now we consider the following equation which says that every integer has a prime factor except for 1 and -1:

If there were finitely many primes then the left-hand side would be closed as a finite union of closed sets, however that would mean {1,-1} was an open set which it is not. Therefore there cannot be finitely many primes. Goldilocks thought this proof was just right.