## August 04, 2005

### 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. Anonymous said...

I love primes, especially the number 13! One small thing: strictly speaking, 1 is not a prime, since a prime needs to be non-invertible.

Goldbach is one of my favourites! It has been shown that any even number is the sum of at most six primes.

Suresh Venkatasubramanian said...

not to mention the "Indian connection": for a long long time, no one knew how to test whether a number is prime efficiently (specifically, in polynomial time), till a few years ago, when Agarwal, Kayal and Saxena (the first a prof at IITKanput, and the latter two students) proved that indeed one can test whether a number is prime in polynomial time. Anonymous said...

Thanks, Suresh for that reminder. If I am right, that paper is not yet published. Any ideas why?

Tanuj said...

super stuff, d!

The Tobacconist said...

Delightful read. Loved Euclid's proof. It is elegant. There is joy in just reading it.

What's interesting though is that numbers are a result of our perceptual abilities. It is how we choose to quantify the world around us. I guess more than telling us about the world, I believe, they are capable of telling us a lot about ourselves.

km said...

Mmmmm..primes...anyone for prime beef steak?

Ramanujam's 1729 is not a prime. So don't nobody mention it.

eV said...

Had posted the foll quote on my blog last month.

"Prime numbers are what is left when you have taken all the patterns away. I think prime numbers are like life. They are very logical but you could never work out the rules, even if you spent all your time thinking about them." - 'The Curious Incident of the Dog in the Night-time' by Mark Haddon.

Amit said...

Prime Numbers - I could not figure them out even in my prime.

different post --- really interesting

zap said...

What about odd numbers being expressed as the sum of 2 prime numbers , one of them being 2 ? Any mysteries on that one?

Suhail said...

Wow! Dilip, I love these ocassional science/math posts..keep em coming more often.

And Euclid's proof is indeed so beautiful!

Iyer the Great said...

Wonderful post.

Prime numbers show patterns and have "a meaning" only in aggregate as individually they are "outcasts" - with no relationship to any other numbers.

Anand said...

Dilip -- Very nice post. I was thinking of writing about primes @ Locana after reading your FLT post. Now I'm glad that I did not write! You do it much much better.

Vishnu -- AKS paper is published. In one of the most prestigious math journals - Annals of Mathematics, September 2004 issue.

Dilip -- Let me just add two more results here. One is from the 19th century, and the other from 2004.

First one is due to Dirichlet which says that there are infinitely many primes in any arithmetic progression as long as the starting integer and the common difference have no common factor. i.e., take any two numbers a and b which have no common factors. Then infinitely many members of the sequence
a, a+b, a+2b, a+3b, ...
are primes. It's a beautiful piece of work.

The 2004 result is due to Terrence Tao and Ben Green. This is going to be published in the Annals of Mathematics as well. They proved that there are arbitrarily long arithmetic progression of primes. i.e., given a number k there is an arithmetic progression of k numbers each of which is a prime number. For instance if k=10, here's one such progression:
199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089. (Common difference=210).
The proof is quite involved and uses techniques from other branches of Math such as Ergodic Theory and Dynamical Systems.

Compare the above two results. One proved around 150 years ago. Another proved just last year. Beautiful!

Dilip D'Souza said...

Wow, I'm thrilled at the responses here!

Thanks for pointing out the IIT angle, Suresh. I should have included that.

zap, there's no mystery there: odd numbers being expressed as the sum of 2 prime numbers , one of them being 2 is impossible. This would mean that every odd number is greater by 2 than a prime; which means that every odd number is prime. Are you thinking of something else?

Anand, the Dirichlet and Tao/Green results are delightful! I think I knew of the Dirichlet one, but had absolutely no idea of the Tao/Green. Any easy way to find a (the?) sequence, given a k? Anonymous said...

Anand, thanks for the info on the AKS paper, and more importantly on the beautiful results. This page says that the Tao-Green proof was nonconstructive. Anonymous said...

No way to find a sequence for a given k from their proof. Vishnu's link has a lot more details. Anonymous said...

I did try to prove Goldbach's theorem a few years ago before realizing that a class nine guy's knowledge was woefully inadequate.

And I know Manindra Agarwal personally. Claim to fame, kya? Anonymous said...

I've been thinking about writing on Maths for the past one month. It seems so hard to write for the lay man even though my own knowledge is limited to high school maths.

How do you do it? Anonymous said...

-----------------------
The Number Empire

Shashikant Kore said...

What about the cool Prime Number Spiral?

Philip R Dutton said...
This comment has been removed by the author.
Philip R Dutton said...

As an alternative thought, consider the axioms of arithmetic. List them on paper and erase the ones related to division and multiplication. Now given that set of axioms, what is a prime number?

There is much to be said about this line of thinking but no one seams to be talking on these terms. Anonymous said...

which number less than 100 has the most prime factors. Anonymous said...

Is there a relation between the conjectures that every even number is sum of two prime number 2k>2 and every even number is differnece made by two prime numbers? I mean if one of them is proven, can the other be also proven? Anonymous said...

Here is something interesting. Is it proven that there are infinietly many perfect squares when increased or decreased by a certain natural number s remains perfect square? I have got the method and i can tell infinitely many answers other than Fibonacci's answer for 5 is
(41/12)^2+5=(49/12)^2
(41/12)^2-5=(31/12)^2
(2566561/206640)^2 This is the answer for 31.
Infact it is related to the mystery of prime numbers but..... hey not to say everything on the veiw check for something new. Anonymous said...

there is a good connection between primes and ramanujan primes . has anybody studied that Anonymous said...

ramanujan ko land cancer or us ke biwi ko choot cancer ho gaya tha so he was not able to continue to reveal enormous discoveries Anonymous said...

k^2 - x^2 = pq

k is any number that is not a prime, x is a number less than k and greater than 0 p and q are primes
goldbach's conjecture proven
if above is right