View Single Post
Old 2003-05-19, 23:11   #4
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2×59×83 Posts
Default Re: The first (non-merseinne) 10 million-digit prime number!

Originally Posted by ron29730
Since by adding 1 to N! gives a prime number (N! + 1 cannot be factored by any number =<N)
Simply because (N! + 1) (or (N! - 1), for that matter) is not divisible by any prime <= N does not make it prime. Even if you modify the factorial and instead use the product of all primes <= N (a la Euclid in his beautiful proof of the infinitude of primes), N! +- 1 need not be prime, e.g. (2*3*5*7*11*13+1) = 59*509 and (2*3*5*7*11*13*17+1) = 19*97*277.

Now, if one knew every prime <= R (the current record holder), one could form the product of all these, add or subtract one, and the result would be guaranteed to have no factors <= R, i.e. one would have implicitly found a new record-size prime. One can do similar stuff like this with Mersennes: if R is the largest-known Mersenne prime, then 2^R - 1 has no factors < 2*R+1,
i.e. is either an even bigger prime or decomposes into factors bigger than R. But these types of constructions don't qualify for record-prime status: that requires an EXPLICIT prime. Looks like the EFF gets to hold on to their $100K for a little while longer.
ewmayer is offline   Reply With Quote