Prime time

Must sound odd to speak of certain numbers as being under-appreciated. You would use that to describe, for example, an actor's performance in a film. But numbers? Yes, numbers, and I'm going to start setting things right with this piece! Prime numbers are the world's least appreciated numbers and this is simply intolerable! I won't let this go on! I can't take it any more ... hmm. Excuse me.

But think of it. We all love our 8s and 9s and 420s. But how many of us stop to give a kind thought to the 3s, the 7s, the 23s, the 109s? Very few. A great shame.

Right, but quickly, what is a prime number? One which has no factors apart from 1 and itself: that is, it can only be divided by 1 and itself.

Consider 15. Its factors are 1, 3, 5 and 15 itself, meaning it can be divided evenly by any of those. Similarly, the factors of 32 are 1, 2, 4, 8 and 16. Neither 15 nor 32 is prime.

Now take 17. It can only be divided by 1 and 17. 43? Just 1 and 43. 131? 1 and itself. These are primes. The smallest prime is, trivially, 1. 2 is the only even number that's prime (since every other even number is divisible by 2).

In a lot of ways, primes are like the rocks on which our entire number system is built, without whose vigilant presence it would come tumbling down. I say this partly because every non-prime can be factored into primes. For example:

65 = 5 x 13
420 = 2 x 2 x 3 x 5 x 7

So what's so interesting about primes? Start here: there is a smallest prime, but is there a largest one? In about 300 BC, Euclid, the great Greek mathematician, answered that in a wonderful example of elegant reasoning.

Assume that there is a largest prime: call it P. Now multiply all the primes between 2 and P, and add 1. Call the result N. That is:

N = (2 x 3 x 5 x 7 x 11 x ... x P) + 1

What can we say about N? To begin, it is clearly greater than P. Is it divisible by 2? No, because that division leaves a remainder of 1. Is it divisible by 3? No, another remainder of 1. In fact, it is not divisible by any prime between 2 and P, for 1 is left over each time.

So is N prime? If so, we have found a prime larger than P. If it is not, it can be factored into primes. But none of those prime factors is between 2 and P (remember the remainder of 1). Therefore, N must have a prime factor larger than P. Again, we have found a prime larger than P.

Either way, we have a prime larger than P. Therefore, our assumption that there is a largest prime is wrong, and there is, in fact, an infinite number of primes. Take that!

(I love that proof).

So that's something we know about primes. More interesting is how much we just don't know about them. Even simple things. For example, it seems that even numbers can be expressed as the sum of two primes. Consider:

24 = 7 + 17
82 = 3 + 79
18 = 5 + 13

Simple, right? So is every even number the sum of two primes? The surprising answer: we have no idea. This is the famous Goldbach conjecture. It seems true: pick any even number you like and you can find such a sum. But in mathematics, seeming is quite different from proving, and the Goldbach conjecture remains unproved. There's a prize on offer if you can prove it before 2020, so try your luck.

Something else about primes. There are several "prime pairs" -- two primes that differ by two. Examples: 3 and 5, 29 and 31, 10,006,427 and 10,006,429. Now Euclid showed that there are an infinite number of primes. Are there an infinite number of prime pairs? The surprising answer once again: we have no idea. While most mathematicians are sure the answer is "yes", this is still another unproved conjecture. (No prize, though).

And one more thing to chew on. In the one hundred numbers between 9,999,900 and 10,000,000, there are nine primes. But in the next one hundred numbers, 10,000,000 to 10,000,100, there are only two. What's going on here? Is there any order at all to prime numbers, to how they are distributed?

There is. But only if you look at them as a collection. Much as you can say things about all of India -- 40% is illiterate, for example -- that you cannot say about individual Indians (is 40% of you illiterate?) or even a small set of Indians (are 40% of your friends illiterate?), prime numbers show patterns in the aggregate.

And when you understand that, you can ask interesting questions. For example, how many primes are there less than a given number? There are 25 primes less than 100, 46 below 200, 168 below 1000, 1229 below 10,000. Is there a pattern here?

Well, let's see. Call P the number of primes below a number N, and here's a table listing N, P and the ratio of N to P:

N	P	N/P
10	4	2.5
100	25	4.0
1000	168	6.0
10,000	1229	8.1
100,000	9592	10.4
1,000,000	78,498	12.7
10,000,000	664,579	15.0

Look at how the ratio grows: as N increases by a factor of 10, N/P increases by about 2.3.

For mathematicians, this is one of those "Aha!" moments: the natural logarithm of 10 (never mind what that is, except it involves the intriguing number e) is about 2.3. This clue led Carl Gauss, at 15 in 1792, to propose the famous prime number theorem -- and this one has been proved: as N gets larger, the ratio N/P gets closer and closer to the natural logarithm of N.

Or, the number of primes less than a number N is approximately N divided by its natural logarithm.

Order in those primes, at last!

"Upon looking at these numbers," wrote the mathematician Don Zagier of primes, "one has the feeling of being in the presence of one of the inexplicable secrets of creation."

I'm convinced.