|
%I #12 May 05 2021 20:55:29
%S 150851,452051,1325843,1441091,4974971,5016191,15139199,19020191,
%T 44695211,101276579,119378351,128665319,152814531,187155383,203789951,
%U 223782263,307367171,387833531,392534231,470579831,505473263,546748931,626717471,639969891,885510239,974471243,1147357559
%N Lucasian pseudoprimes: composite numbers k such that 2^(k-1) == k+1 (mod k(2k+1)).
%C These are pseudoprimes k == 3 (mod 4) such that 2k+1 is prime.
%C 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
%C 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)).
%t Select[Range[10^7], CompositeQ[#] && PowerMod[2, #-1, #*(2*#+1)] == #+1 &] (* _Amiram Eldar_, Apr 26 2021 *)
%Y Cf. A001567, A002515, A081858.
%K nonn
%O 1,1
%A _Thomas Ordowski_, Apr 26 2021
%E More terms from _Amiram Eldar_, Apr 26 2021
|
