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/