## 09 Jul Mathematical Quest 3: Prime Numbers

Download this post as PDF (will not include images).

*The editor of the English section of Gonit Sora, writes a monthly column devoted to mathematics in a teen magazine called Young NE. The editor of Young NE was kind enough to grant us permission to republish the column after it appears on print. Below is the column that appeared in Vol 1, Issue 3, July 2013 of Young NE.*

[ad#ad-2]

In this column, I shall talk about a very very special class of numbers called **prime**** *** numbers*. You probably know these classes of numbers, but didn’t think them to be very useful. My goal in this column is to give you some flavours of what these numbers have in store and why are they important?

First let us define these prime numbers. *Numbers** **which** **have** **only** **two** **positive** **factors** **are** **called** **prime** **numbers*. For example, 2, 3, 5, 7 and 11 are the first five prime number. 9 is not a prime number because it has three positive factors, not two. Prime numbers have been a source of wonder, mystique and much deliberation for more than three to four millenium now. It all started when **Euclid**, the famous Greek mathematician wrote down his classic textbooks called **‘The**** ****Elements’**. Therein Euclid stated and proved a theorem which we now know as the fundamental theorem of arithemetic. What does this theorem say? It says that given any positive natural number, we can always break it down into product of prime numbers or powers of prime numbers in a unique way. For example if we consider the number 100, then we have 100=2x2x5x5 and this representation is unique. This happens for any positive natural number.

In light of the above discussion we see that these prime numbers are the building blocks of all our numbers that we normally use. Thus their importance can neither be denied nor overlooked. But this is not the sole reason why prime numbers are important. They have a vast use in our day to day life also.

Have you seen someone use an ATM? Or perhaps you yourself have used one? Or maybe you bought the latest Dan Brown book on flipkart.com? Or perhaps some of you might have recharged your mobile phone online? Whatever be the case, you had to write in your Debit/Credit card number and then voila your bill was paid and you needn’t worry about anyone stealing your information. But have you wondered how this information goes from the website to the merchant and then that merchant determines what amount to deduct and return you the message? All this happens in a fraction of a second, and that is because of the beauty of mathematics. In this whole scenario of online transactions or ATM withdrwals, prime numbers play a major role. What happens is that there will be two very very large prime numbers, and then they will be multiplied together to get a huge number say X. Now X will be given by the merchant to the bank and then the bank will send in another large number, say Y to the merchant. If one party knows one of the prime numbers originally used then the number Y so generated can give you X that the merchant or the bank sends. This is infact a very famous system called the RSA cryptosystem and this system is used almost in every online transactions and is considered one of the safest ways to send in such information so that only the person for whom the information is meant to will be able to extract it, while the rest of the people won’t be able to learn anything.

Now that we have seen the importance of primes, then do we know how many prime numbers are there exactly? In fact, we do. The answer is infinite, that is the primes are a never ending sequence of numbers. This was again proved by Euclid in his Elements. It is also known that the primes become rarer and rarer as we go on. For instance between 1 and 100 there are 25 primes, that is 25% of the numbers are primes. Between 1 and 1000 there are about 16.8% primes and so on. We see that the density of primes goes on decreasing as we increase our interval of obeservation. This fact, combined with a lot of ingenuity led to what is called the prime number theorem, a very important theorem in modern mathematics. Unfortunately, we need to understand a lot of math before we can state this result, so I shall skip it.

Now that we know there are infinitely many primes, then is there any way in which we can determine whether a given number is prime or not? For small number it is a relatively easy task and there are many ways in which we can do it. But for larger numbers this becomes a major issue and requires lots of computation. For a long time, no such method existed to check whether a number was prime or not in a finite amount of time. But in 2001 there came a landmark paper by three Indian computer scientists where they showed that an algorithm existed which allowed a computer to determine whether a given number is prime or not in a time that is efficient. These three men were Prof. Manindra Agarwal, Neeraj Kayal and Nitin Saxena from IIT Kanpur. Kayal and Saxena were then final year engineeting students when they found this remarkable result.

It is also worth noting that Neeraj Kayal was born and brought up in Guwahati. Kayal did his schooling from Don Bosco, Guwahati and then Cotton College before going to IIT Kanpur where he also did his PhD, then he went to Princeton University, Rutgers University and many other places of repute before finally settling as a researcher in Microsoft Research, Bangalore.

These were just a glimpse of what prime numbers are, there are many more such prime facts and oddities to share which I leave it for some other time. You can call/SMS me at +91-80119-02141 or email me at [email protected] with your comments, querries, corrections, criticisms, etc.

*[ad#ad-2]*

## Juas

Posted at 09:14h, 27 AprilHey TBrown,Thank you for the reply and for the thoughts. The aelertd version of the sieve I created (using the above understanding of the pattern) works differently than the standard sieve… A standard sieve does the following 1) Everything is marked as “unknown” 2) 1 is treated special 3) 2 is marked as prime and all of the factors of 2 are then removed 4) 3 is marked as prime and all of the factors of 3 are then removed 5) The routine then looks for the next “unknown” array item and considers it prime a. It then flags all of the factors for that prime and goes to the nextIn the above model, primes are found based on the next “unknown” value… The sieve I created works differently. 1) It initially marks everything composite 2) 2 and 3 are marked prime (because they a standalone primes) 3) It then flags the primes based on the (1 + 6x) and (-1 + 6x) pattern 4) It then starts at 5 and only flags the 4th and 2nd (as shown above) multiples of the numbers in the line a. Based on the pattern shown in the images… 5) There is no need to continue once you make it past half way in the sieve a. That is because after half way, there would be no remaining factorsBased on the reduced amount of processing, the above model works quicker. However, all of that was derived from closely examining the pattern.I really like the way you phrased exclusionary vs. inclusionary … That makes complete and perfect sense. Unfortunately, one can look at the exclusionary pattern and know for certain there is not an inclusionary one.