|
|
A343679
|
|
Lucasian pseudoprimes: composite numbers k such that 2^(k-1) == k+1 (mod k(2k+1)).
|
|
0
|
|
|
150851, 452051, 1325843, 1441091, 4974971, 5016191, 15139199, 19020191, 44695211, 101276579, 119378351, 128665319, 152814531, 187155383, 203789951, 223782263, 307367171, 387833531, 392534231, 470579831, 505473263, 546748931, 626717471, 639969891, 885510239, 974471243, 1147357559
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
These are pseudoprimes k == 3 (mod 4) such that 2k+1 is prime.
Proof. Let q = 2k+1 be prime, where k == 3 (mod 4) is a pseudoprime. We have q == 7 (mod 8), so 2 is a square mod q, which gives 2^((q-1)/2) == 1 (mod q), by Euler's criterion. Thus, 2^k == 1 (mod q), which implies 2^(k-1) == (q+1)/2 (mod q), so that 2^(k-1) == k+1 (mod q). The conclusion that 2^(k-1) == k+1 (mod kq) follows from the assumption that k is a pseudoprime and from the Chinese remainder theorem. - Carl Pomerance (in a letter to the author), Apr 14 2021
Note that if p is a Lucasian prime, i.e., p == 3 (mod 4) with 2p+1 prime; then (2^p-1)/(2p+1) == 1 (mod p), hence 2^p-2p-2 == 0 (mod p(2p+1)), so 2^(p-1) == p+1 (mod p(2p+1)).
|
|
LINKS
|
|
|
MATHEMATICA
|
Select[Range[10^7], CompositeQ[#] && PowerMod[2, #-1, #*(2*#+1)] == #+1 &] (* Amiram Eldar, Apr 26 2021 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|