Prime time

As was reported at various places (see, e.g., the BBC), in August this year a prime number (in particular a Mersenne prime) was discovered which was larger than any previously known prime - the first 10 million digit prime number! The number, 2^43112609-1, was discovered by a distributed computing project called GIMPS, the Great Internet Mersenne Prime Search. Congratulations to everyone involved!

I have been wanting for a while now to introduce more non-programming related content to this blog and the discovery of this new prime has motivated me to write somewhat regularly about issues in number theory and about prime numbers and related concepts especially. I think prime numbers are very misunderstood, or perhaps it would be better to say "under-understood". Almost everybody understands what a prime number is, but very rarely is anybody ever told why it is that mathematicians get excited by them. The BBC story linked to above, for example, offers not even a token explanation as to why millions of people donate their spare computer power to a world-wide collaborative effort to find large new primes, or why organisations like the EFF are willing to offer large cash prizes for people who find primes. Do prime numbers actually have practical uses? Yes! Are there good intellectual reasons to be more interested in them than all the other, composite numbers? Yes! Is there something special and enchanting about primes that causes people to become obsessed with trying to understand them? Yes! But it's an exceedingly rare school teacher who mentions any of these things when teaching kids what a prime number is. To be fair, perhaps that in particular isn't unreasonable - in Australia, at least, children are taught what a prime number is at a fairly young age, too young to really appreciate many of these things. Perhaps the problem is that primes, and number theory in general, aren't ever revisited later in a child's education, where these things could be made clear.

I have personally fallen "victim" to this. Until I switched from a physics to a mathematics major in university, I had no idea why anybody would particularly care about prime numbers. I thought that the division of numbers into primes and composites was no more compelling than the division of numbers into odd numbers and even numbers, into perfect numbers and imperfect numbers, into triangular, square, etc. numbers. Many of these distinctions struck me as rather arbitrary and uninteresting ones, based on frankly quite childish and superficial observations. I still hold this opinion today for most of these divisions, but I have learned a lot about primes (and their abstract algebraic generalisations!) since then and now understand that they certainly do not belong in the same mental pigeon hole as perfect or square numbers.

In an attempt to help spread some of this understanding, over the next few months I'll try to write entries explaining some of the reasons prime numbers are interesting, some of their practical applications, explain some simple algorithms to do with prime related concepts (like primality testing and factorisation) and point out some of the many compelling mysteries about primes that continue to capture the attention of mathematicians today. A survey of interesting stuff to do with primes will take readers all the way from ancient Greece, around 300 BC, to the early internet days of the 1970s and 1980s, with a few detours through 17th century France. I'll try my best to make the material interesting and accessible to non-mathematicians. Please look forward to it!