A343679 Lucasian pseudoprimes: composite numbers k such that 2^(k-1) == k+1 (mod k(2k+1)).

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

Offset: 1

Author

Thomas Ordowski, Apr 26 2021

Keywords

• nonn

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)).

Crossrefs

Cf. A001567, A002515, A081858.

Programs

Mathematica

Select[Range[10^7], CompositeQ[#] && PowerMod[2, #-1, #*(2*#+1)] == #+1 &] (* Amiram Eldar, Apr 26 2021 *)

Extensions

More terms from Amiram Eldar, Apr 26 2021