## Re: [PrimeNumbers] Digest Number 1340

Expand Messages
• If 2^p -1 is a prime number then 2 ^p does not have a divisor (
Message 1 of 2 , Jun 27, 2004
If 2^p -1 is a prime number then 2 ^p does not have a divisor (< 2^ p -1 and
> 2) which yields a remainder of 1. I call this a prime 1 in distinction
with ordinary primes which are prime 0. There are of course other higher order
primes prime 2 etc.
Because 2^p is factorable, it might be easier to search for prime 1 numbers.
If one is found then 2^p - 1 would be a Mersenne prime. Does this help?

If I follow what you are saying, it does indeed help and is already
being used by many programs, including George Woltman's Prime95 and
the factoring programs of the mers package that I maintain.

What those programs do - instead of actually calculating 2^p - 1 and
then dividing it by each possible factor - is calculate the power of 2
modulo each possible factor and see if the result is 1. Since the
possible factors being tested are much smaller than 2^p - 1 itself,
the modulo (remainder) operations are much faster ... so much faster,
in fact, that they easily more than making up for having to
recalculate 2^p every time. But the programs also don't calculate 2^p
modulo the possible factor by doubling p times; there's a faster way
involving squaring (from Knuth, if I recall correctly).

But even that isn't fast enough to prove that 2^p - 1 is prime except
for _very_ small values of p (less than 100, say); there are simply
too many possible factors less than the square root of 2^p - 1.
For that, the Lucas-Lehmer test is needed. See George's web site,
below, and others for more details.

Will

George Woltman's site, including Prime95 (free) and GIMPS, the Great
Internet Mersenne Prime Search, discoverer of the last seven largest
primes known:
http://www.mersenne.org/

My own Mersenne related web pages, including the mers package (free):
http://www.garlic.com/~wedgingt/mersenne.html
Your message has been successfully submitted and would be delivered to recipients shortly.