Prime Number Series

2, 3, 5, 7, 11, … . What do these numbers have in common? They are all primes: they are not divisible by any number except 1 and themselves. That is an intriguing property for a number to have. It reminds us of the fundamental particles in physics; indivisible units that make up all the atoms and molecules we find in nature.

And indeed, the primes do play such a fundamental role in mathematics. If you take a whole number that is not prime, say 12, you can break it down into its divisors, for example 12=2×6=3×4. Each divisor that is not prime itself can be further broken down: 12 = 2×6 = 2x2x3 and 12=3×4=3x2x2. Every divisor in this example is now prime, so we stop. For a number other than 12 you may have more steps to go, but ultimately you will also end up with an expression of your number as a product of primes. And what is more, this expression is unique: the primes might appear in a different order but any such expression of a number will always contain exactly the same primes.

This result, that every whole number is a product of primes in a unique way, is called the fundamental theorem of arithmetic. It made its earliest appearance in Euclid’s famous book The Elements in around 300BC. Euclid also showed that there are infinitely many primes: they never run out as you move up the number line.

So is that a done and dusted piece of mathematics then? Perhaps one might want to add to Euclid’s findings some recipe for spotting primes and, if a number isn’t a prime, a quick and easy way of factoring it into its prime components. But it turns out these simple requests land you right in the thicket of modern mathematics and computer science.

The problem is that there isn’t a simple recipe for spotting primes. Checking whether a given number is prime requires more and more calculational power as the number gets larger. Computer geeks have turned the quest for larger and larger primes into a mission. At the forefront is the GIMPS project, the longest-running distributed computing project in the world, which uses the donated power of thousands of idle computers to hunt for larger and larger primes. The record at the time of writing, discovered on January 25 2013, is a 17,425,170 digit number, more conveniently written as 257885161-1.

This may sound like frivolous fun (if you are that way inclined) but there is a serious aspect to such prime problems. While checking whether a number is prime is hard, factoring a non-prime number into its prime components is even harder when the number is large. The mechanisms that encrypt your bank details when you send them over the internet rely on this fact. The receiver takes two large primes and multiplies them, which is easy to do. It then sends the resulting number N to the sender, openly and publicly. The sender uses N to encrypt the message (using a standard method). Decrypting the message, however, requires knowledge of the prime factors of N. The receiver has that knowledge, that’s how it got N in the first place, but anyone intercepting the transfer would need an unfeasible amount of computing power (if the original primes are large enough) to factorise N and crack the code. So the safety of your bank details, and many other secret messages, depends on the inexhaustible supply of primes.

Back in the land of pure mathematics the primes are a hot topic for another reason: they lie at the heart of unanswered questions that have been bugging mathematicians for centuries. Some of those questions are so straightforward you might come up with them yourself with a bit of tinkering. For example, playing around with even numbers you might find that, as long as they are greater than two, they seem to always be the sum of two primes: 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5, and so on. This is true for any even number mathematicians have ever checked, so it is probably true for all of them.

It would make a pleasing result, showing the primes are fundamental building blocks not just in a multiplicative, but also in an additive sense. The trouble is that so far nobody has been able to prove that this conjecture, so easily stated, is actually true. It has been attributed to the German mathematician Christian Goldbach, who first mentioned it in a letter in 1740, and it now carries his name: the Goldbach conjecture.

Another thing you might notice is that primes often seem to come in pairs: 3 and 5, 5 and 7, 11 and 13, 17 and 19, and so on. Are there infinitely many such pairs? Can you always be sure to find another pair as you move up the number line? Again, the answer to this twin prime conjecture is unknown, despite the conjecture having been around for over 150 years.

The twin prime conjecture hints at a more general question: how are the primes sprinkled among the other numbers? In general they do seem to get sparser as you move up the number line and we know that, as well as twins, you can find arbitrarily long gaps between them. The prime number theorem gives an estimate of the number of primes there are below a given number n. It’s approximately n/ln(n), where ln(n) is the natural logarithm of n. This estimate becomes more and more accurate as n gets larger.

But can we say more? The answer lies concealed in what is perhaps the hardest open problem in mathematics: the Riemann hypothesis, named after the 19th century mathematician Bernhard Riemann. The mathematics is complex, but a proof of the Riemann hypothesis would reveal much about the ebb and flow of primes on the number line. And it would win the person who finds it $1 million from the Clay Mathematics Institute, who offered one of its Millennium Prizes for its resolution. Those atoms of number theory, first discussed over 2000 years ago, still have a lot to offer today!