In this short series of articles, I’m writing about mathematical questions we don’t know the answer to – which haven’t yet been proven or disproven. This is the third article in the series, and across two parts will discuss various open conjectures relating to prime numbers.

I don’t think it’s too much of an overstatement to say that prime numbers are the building blocks of numbers. They’re the atoms of maths. They are the beginning of all number theory. I’ll stop there, before I turn into Marcus Du Sautoy, but I do think they’re pretty cool numbers. They crop up in a lot of places in maths, they’re used for all kinds of cool spy-type things including RSA encryption, and even cicadas have got in on the act (depending on who you believe). Since the dawn of time [citation needed], mathematicians have been fascinated with what prime numbers are, how many there are (see below), tests for primality, and crucially, finding a pattern in which numbers are prime and which aren’t. So far, the answer to that one has eluded us.

Proving that there are infinitely many primes is relatively simple. Imagine for a moment that there aren’t – there’s a finite number of them, and we can list them all. In that case, I can take every number in the list, multiply them all together, and then add one. The result of doing this will be a number that’s decidedly not already in the list – it will in fact be quite a lot bigger than anything in the list. But crucially, it will also not be divisible by any of your existing prime numbers. Strictly speaking, dividing by any of those numbers will always leave remainder one. So, this new number must also be either a prime number, or have a prime factor, which wasn’t already on the list! I can pull this trick as many times as you like (I have infinite patience), so any finite list you can give me won’t contain all the primes. Hence, there are infinitely many.

This proof, attributed to Euclid, is a little bit subtle – sometimes it’s misinterpreted as implying that multiplying these numbers together and adding one will always give a new prime number ((Strictly speaking, if we live in a universe where the only prime numbers are the ones on your finite list, this new number is in some sense a prime number, as it has no prime factors other than itself. But if the only prime numbers are those on your list, then it’s by definition not a prime number. This is why it’s sort of confusing.)). Depending on the list of primes you give, it sometimes will – and sometimes the number will be composite, but since it’s not divisible by anything in your list of primes, its list of prime factors must contain some you’ve missed, hence your list was incomplete.

For the purposes of this proof, your list of primes can be any arbitrarily chosen list of prime numbers. However, if you in particular look at the case where you multiply together the first N known primes (starting with $2,3,5,7\ldots$) and then add one, this gives you a set called Euclid numbers (for obvious reasons).

And here comes our first open conjecture – which Euclid numbers are prime? We know some aren’t – the smallest composite Euclid number is the 6th, which is $(2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031$, which is $59 \times 509$. But many of them are. The standard maths question would be to ask, are infinitely many of them prime?

In fact, the answer to the question is: we don’t know. It’s unknown whether there are an infinite number of prime Euclid numbers! So there’s already an open problem to play with. If you do start playing with Euclid numbers, your first challenge is to work out why for all Euclid numbers past the third one, the last digit is a 1.

The above proof is a lovely example of how the properties of prime numbers can be used to determine facts about the group. It’s also relatively easy to prove that any prime number (from 5 upwards, which some would argue is the first proper prime number), when squared, is one more than a multiple of 24. If you want to have a go at proving this, try thinking about what the remainder will be on dividing a number.

How do we check if a number is prime? Well, there’s one obvious way, which is to try dividing it by things. If you want to be certain something is prime, you’ll need to check every number you could divide it by up to its square root (beyond which you’ll find, if it is divisible by that number, you’d have already discovered as much when you checked the other, smaller factor). This is as super-effective as a Raichu’s ThunderShock attack, but not particularly efficient. As soon as you have any decent size of number, you find yourself checking an impractical number of divisors, which eats up all your computer time, let alone pencil lead if you’re doing it by hand.

Luckily, mathematicians have come up with several more efficient primality testing methods. Wilson’s theorem gives a nice, if still fairly inefficient, alternative to brute force hacking; but the most widely used types of test are probabilistic. The way I remember this being explained to me in first year of uni was, as long as you run the test sufficiently many times that the probability of the test having given a false positive result is smaller than the probability your computer has made an error, you’re fine. Or something. It’s also easier to test primality for certain types of primes – for example, Mersenne primes, which are primes of the form $2^p – 1$ (where $p$ is prime).

If you haven’t heard of Mersenne primes, you’ve not been reading the news very carefully lately, but the nature of these numbers means they’re easier to test for primality. Wikipedia mysteriously states that ‘fast algorithms […] are available‘; the only one I’ve looked at in any depth is the Lucas-Lehmer primality test, which was originally developed as far back as 1856, and involves taking a predefined sequence of integers, and checking whether the $(p-2)$th one is zero modulo $2^p -1$. If it is, then $2^p – 1$ is prime. Easy peasy, huh? These types of fast algorithms are why the top ten biggest known prime numbers are all Mersenne primes (the eleventh isn’t.)

So, we have a pretty good handle on how prime numbers are defined, how many of them there are, and how to check whether a number is prime. But what don’t we know? You’ll have to read the next post to find out.

To be continued next week.