Sorry, an error occurred while loading the content.

## an interesting mersenne property i just found...

Expand Messages
• So I was looking at the Mersenne numbers yesterday and found a curious property: 3^(2^(p-1)) = -3 (mod 2^p - 1) if (2^p - 1) divides S(p-1). For the sake of
Message 1 of 6 , Mar 1, 2005
So I was looking at the Mersenne numbers yesterday and
found a curious property: 3^(2^(p-1)) = -3 (mod 2^p -
1) if (2^p - 1) divides S(p-1).

For the sake of reference, I'm using S(1) = 4, S(n+1)
= S(n)^2 - 2. Also, by 'Mersenne number' I mean "let
p be prime, then 2^p - 1 is a Mersenne number, namely
M_p".

I got this result by taking the proof of the
sufficiency of the Lucas-Lehmer test (see
http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html)
and doing some squaring and modding. I haven't been
able to show (yet?) whether the property I found is a
sufficient condition for primality, but so far it
hasn't found any false positives or missed any actual
primes (tested up through 521 at the time of this
writing). It does seem to be (at least) a necessary
condition.

Of course... now that I look more closely at my code,
this test appears to be one cycle longer than the
Lucas-Lehmer test, so maybe it isn't really worth
pursuing. Hard numbers: it was 6 seconds less time to
check M_11213 (94 seconds for Lucas-Lehmer, 88 for my
method, both using algorithms written in Lisp, run
under SBCL 0.8.19 on a 566MHz Celeron), and a little
less memory too...

Joseph.

__________________________________
Do you Yahoo!?
Yahoo! Sports - Sign up for Fantasy Baseball.
http://baseball.fantasysports.yahoo.com/
Your message has been successfully submitted and would be delivered to recipients shortly.