Predicting Primes

One of the few mathematical problems that has endured throughout centuries and is the bane of every mathematician is predicting prime numbers. As anybody who has passed the second grade knows, a prime number is a number that cannot be divided into two integers by any integer, discounting 1 and itself. At first glance, one might think, 'Hey, this doesn't seem too difficult! All we have to do is take a number and check whether any other number divides it!'

Well, that's not exactly what the mathematicians of today are trying to do. They aren't trying to test a number to check if it's prime or not. What they are trying to do is devise a formula that allows them to generate the next prime number after one has been discovered; a formula which would allow them to find out the next prime number after the largest that has been discovered till date- which happens to be (2^77232917 – 1). Imagine trying to figure out a prime number after the behemoth numbers that will exist after this one! It is surely not as easy as one might think, and I'm going to tell you exactly why we haven't been able to do so up until today.

Firstly, prime numbers are infinite, just like normal numbers. One might believe that there's a hard limit as to how many primes exist, but that is incorrect, as Euclid's theorem proves.

The theorem goes like this- you take the first prime number that exists today (let's call it p1) and multiply it by it's consecutive primes p2, p3, p4.... all the way till the supposed 'last' prime, pN. Then, you add 1 to the product x, making the theorem look like this:

x = (p1*p2*p3*p4*p5*p6*.....*pN) + 1

If x is another prime, then it's a prime that exists after pN, making it so that pN wasn't the last prime after all! And, if x isn't a prime, that means it is divisible by a prime that cannot be found in the list you took, as no integer can divide 1 into another integer (remember, you added 1 to the result!). Thus, primes are infinite.

Secondly, there is no pattern to primes. Like there is a pattern to even numbers, there is no pattern no primes, mainly because, of course, they do not share a common divisor besides 1. Of course, mathematicians are working to establish a pattern, but their effort, though amazing, is yielding somewhat lackluster results. Understandable, though frustrating.

What we do have with regards to primes, however, are what we call primality tests; formulas which we may use to check whether a number is prime or not. While they do not actually predict primes, they considerably speed up the process of finding primes. A popular example is the Mersenne prime formula- you take 2 to the power of a prime number and subtract 1 from the result- it gives a prime number. It is represented in this manner:

2 ^p −1, 

where p is the prime number.

You may recognize that the largest prime discovered till date is also a Mersenne prime- which of course explains that mathematicians are still using the formula- so, it does have some validity. However, primality tests can also sometimes be fooled, and the Mersenne prime test is no exception. If you take p as 11, you will get the result 2047, which is not a prime; it is divisible by 23. Such numbers are called pseudoprimes, and they forbid us from using primality tests with impunity.

Another example is Fermat's little theorem (not to be confused with Fermat's last theorem!) which is of the form-

where a is an integer and p is a prime.

What the theorem entails is that taking an integer a to the power p and subtracting a from the result, p being any prime number, we get a number that is a multiple of p. For example, substituting a for 2 and p for 7 gives us the result 126, which is 7*18, and thus a multiple of p.

But, Fermat's little theorem has its own pseudoprimes, and in this case, they are called Carmichael numbers. The smallest Carmichael number is 561; and indeed, 2^561-1  gives us the number 3.773962 times 10 power 168, approximately, which is divisible by 561. And yet, 561 is not a prime- a quick divisibility test tells us that 561 is divisible by 3. Another Carmichael number is 3031, which yields similar results despite being divisible by 7.