On Thu, 25 Mar 1999 [EMAIL PROTECTED] wrote:
> The following was posted on sci.math recently (not by me, unfortunately):
> **********
> Subject: Mersenne Prime
> From: <[EMAIL PROTECTED]>
> Newsgroups: sci.math
> Date: Thu, 25 Mar 1999 18:10:30 +0800
> Message-ID: <7dd21c$[EMAIL PROTECTED]>
>
> Mp is a Mersenne Prime with odd prime p "iff"
> 3^((Mp-1)/2)=-1 (mod Mp) .
>
> Please mail to : [EMAIL PROTECTED]
> (before 3/30)
> **********
> At first sight, I thought "that's not right", but a few minutes of testing a
> few Mersenne primes and non-prime Mersenne numbers on my TI-92+ has upheld the
> "iff". Can anyone find a counterexample? This is bugging me. Augh!
> S.T.L.
That looks suspiciously like Proths test, though that would be for fermat
numbers, not mersennes, ie. 2^p+1, not 2^p-1, though the reason why you
seen to find lots of tests that work is because the test is based on
a^((Mp-1)/q)=-1 (mod Mp) where q is a factor of n-1, which works for
both numbers since they have 2 as factor. For Mersenne numbers it's not a
working test, since it must be true for all factors.
For a counter example, try M(3)=2^3-1=7, a mersenne prime though
3^((7-1)/2)=27=6 mod 7
The confusion is probably caused by the Proth test being a socalled N-1
test, because it's based on N-1 being trivially factored.
--
Henrik Olsen, Dawn Solutions I/S
URL=http://www.iaeste.dk/~henrik/
Get the rest there.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
