[seqfan] Lucas-Lehmer pseudoprimes
David Wilson
davidwwilson at comcast.net
Sun Jul 15 02:51:33 CEST 2012
The Lucas-Lehmer test is
2^p-1 is prime iff A003010(p-2) == 0 (mod 2^p-1)
for odd prime p.
It turns out that
A003010(n) = A003500(2^n)
so we have
2^p-1 is prime iff A003500(2^(p-2)) == 0 (mod 2^p-1)
Letting k = 2^(p-2), gives
4k-1 is prime iff A003500(k) == 0 (mod 4k-1)
If we ignore the known form of k, this test seems to work for small k ==
2 (mod 6).
This leads to the generalized Lucas-Lehmer primality test
[1] A003500(6k+2) == 0 (mod 24k+7)
This devolves to the Lucas-Lehmer test for Mersenne primes when 24k+7 =
2^p+1 for odd prime p.
Empirically, for n = 24k+7, [1] appears to be true for prime n and a few
composite n (pseudoprimes).
I was able to find the following Lucas-Lehmer pseudoprimes:
Lucas-Lehmer psuedoprimes: Composites n == 7 (mod 24) with
A003500((n+1)/4) == 0 (mod n)
1 1037623
2 2211631
3 4196191
4 7076623
5 9100783
6 11418991
7 15219559
8 21148399
9 29486239
10 32060503
11 36035383
12 56902999
13 64450063
14 69017023
15 112367863
16 134793031
17 184353679
18 211883743
19 243005527
20 287903431
21 365603743
More information about the SeqFan
mailing list