Use Freefind to search this site (or the web)
Site search Web search

powered by FreeFind

Tuesday, August 16, 2005

"Numbers" and "largest primes"

While visiting one of my favorite political websites ( I noticed a post that mentioned the TV series "numbers". The episode in question dealt with codes; in particular one can create a difficult to crack code by using a "key" which consists of the product of two very large prime numbers. The idea is that this key would take years and years of computer time to factor.

So, knowing various large prime numbers has some value.

But, the poster on this site (a poet) said something to the effect of finding the "largest prime number". Well, one thing that is easy to prove is that there is no largest prime number!

Here goes the proof:
suppose there is a largest prime number. Let it be "q".

Now consider the number p = q! + 1 (where q! means 1*2*3...*(q-1)*q, e. g., 6! = 1*2*3*4*5*6 = 720)
Now p cannot be prime as p > q and q was the largest prime. So p has at least one prime factor, call it r. r<= q hence r divides q!. r divides p.
So r divides (p - q!) = 1 which is impossible since no prime number divides 1.
Therefore there can be no largest prime number.

Another way of putting this is that if you know that q is a prime number, you can always find a prime number that is larger than q by finding the prime factors of q! + 1.

Of course, it can be very difficult to perform this factorization, but that is another matter.


Post a Comment

<< Home

View Counter Statsfree hit counter
frontline plus