# Primes aren’t that pesky

Prime numbers. One of many sequences of numbers we introduce to innocent school children and their sponge-like minds. However, despite the simplicity of defining what a prime number is, they are tenacious buggers with little regard for the eye of the modern mathematician. They are also the best example of randomness and structure meeting each other in a natural setting. I’m going to try and explain what I mean here, but first let’s recall how the sequence of prime numbers starts:

$2, 3, 5, 7, 11, 13, 17, 19, \ldots$

This sequence continues forever. That’s right – it doesn’t stop. Mathematicians have tried for thousands of years to find patterns in the sequence of the primes. It’s as if some powerful (yet mischievous) deity decided to scatter the primes randomly in the counting numbers. What a bastard. Anyway, we are a bit better off now then we were thousands of years ago, and we now know some amazing truths about the prime numbers. Each of these truths gives some structure or obedience to the set of primes, and speaks to both the tenacity and intellect of humankind.

One such truth, known as Bertrand’s postulate (or Chebyshev’s theorem) guarantees that you can always find a prime between any number bigger than 1 and its double. For example, there will definitely be at least one prime between 5 and 10, or 100 and 200, or 5000000 and 10000000.

Another result ensures that given any fixed string of digits, there are infinitely many primes which contain this string. If you were to choose the string of digits “1234”, then there are infinitely many prime numbers which contain this string. Here are a few:

12343, 12347, 112349, 123401, 123407 …

The result does not tell you how to find these “string-containing primes”, only that infinitely many of them do exist. What an odd result! What if we were to choose, say, your mobile phone number for a string of digits?

Well, then there are infinitely many prime numbers which contain your phone number within their digits. Indeed, the prime numbers are rather intrusive!

It’s not at all surprising that many people have become mesmerised by the interplay between structure and randomness that presents itself within the sequence of prime numbers. It really is a beautiful thing.

Not only are we concerned with results about finding primes in certain ranges or of a certain form, but we are also interested in primes as fundamental particles of numbers. Ok, so this sounds a bit like chemistry, but it’s well known that every counting number (greater than 1) is either a prime or a bunch of primes multiplied together. For example:

$60 = 2 \times 2 \times 3 \times 5$

So, in some sense, the prime numbers are atoms, and all the other numbers are molecules for they are built up out of primes through multiplication. Amazingly, just like in chemistry, many properties of a number (molecule) can be determined  simply by studying the primes (atoms) which are used to build it.

Here’s a cool example of this. It’s known that every prime number except for 2, is either one more or one less than a multiple of 4. That is, all primes greater than 2 take either the form $4n+1$ or $4n-1$.

Now here’s the cool bit:

A number is expressible as a sum of two squares if and only if in the prime factorization of the number, every prime of the form $4n-1$ occurs an even number of times.

This means that by studying the prime atoms which form a number, we can determine if it can be expressed as the sum of two squares! Consider the number 60. We have from before that:

$60 = 2 \times 2 \times 3 \times 5$

We see that $3$ is a prime which is of the form $4n-1$. However, it is only in the factorisation once, and so does not occur an even number of times. So 60 can not be expressed as the sum of two squares.

On the other hand, let’s look at 90:

$90 = 2 \times 3 \times 3 \times 5$

Again, the only prime of the form $4n-1$ is 3, but this time it occurs twice in the factorisation! This will guarantee that 90 can be written as the sum of two squares! Indeed:

$90 = 3^2+9^2$

The above is one of my favourite results in number theory. It’s one of those results that I can turn to when I need some inspiration to keep going (wow, that’s deep, Adrian).

So there is this beautiful theory built on the fact that numbers can be built out of primes using multiplication. I guess it’s natural to ask the following question: is every counting number the sum of a bunch of prime numbers? Well, not every counting number I guess, for you certainly can’t write 1, 2 and 3 as the sum of prime numbers! This doesn’t bother us too much, as 1 tends to stay out of the business of other numbers and 2 and 3 are prime anyway.

Here are two very famous conjectures, proposed by Christian Goldbach in a letter to Leonhard Euler way back in 1742.

Goldbach’s Conjecture: Every even number greater than 2 can be written as the sum of two primes e.g. $4 = 2 + 2$,    $6 = 3+3$,    $8 =3+5,\ldots$

Goldbach’s Odd Conjecture: Every odd number greater than 5 can be written as the sum of three primes. $7 = 2 + 2 + 3$,   $9 = 3+3+3$,   $11 =3+3+5,\ldots$

So Goldbach believed that not only were primes multiplicative atoms but also additive atoms, and that you don’t need many of them to build up each number.

Anyways, I woke up yesterday to the news that a paper containing a proof of Goldbach’s Odd Conjecture had been submitted by Harald Helfgott, a well known number theorist. Sure, papers like this have been submitted before, but there is a strong belief by many that Harald has indeed done it. This is perhaps due to the amazing work that he had already done on the problem, and that he had already outlined how the proof would work; he just needed to do the calculations.

I’m going to remain optimistic over the next huge chunk of time. To see one of the Goldbach conjectures solved is a once-in-a-lifetime thing. Now if only I could understand the proof…