# [seqfan] Lucasian (pseudo)primes

Tomasz Ordowski tomaszordowski at gmail.com
Sat Apr 17 17:45:25 CEST 2021

```Dear readers!

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

Composites k such that 2^(k-1) == k+1 (mod k(2k+1)) are
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,
1227474431, 1284321611, 1304553251, 1465307351, 1474936871, 1514608559,
1529648231, 1639846391, 1672125131, 2117031263, 2139155051, 2304710123,
2324867399, 2939179643, 3056100623, 3271076771, 3280593611, 3529864391,
3587553971, 4193496803, 4244663651, 4267277291, 4278305651, 4528686251, ...
[Data from Amiram Eldar]

Conjecture:
These are pseudoprimes k == 3 (mod 4) such that 2k+1 is prime.
If so, the name "Lucasian pseudoprimes" will be fully justified.

There are 101629 Fermat pseudoprimes up to 10^12.
Of them 276 are of the type k == 3 (mod 4) with 2k+1 prime.
The first 51 of them are exactly those that I have sent you earlier.
[Amiram Eldar]

The conjecture is easily proved.
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]

Problem:
Are there infinitely many numbers n such that 2^{n-1} == n+1 (mod n(2n+1))
?
These are primes and pseudoprimes n == 3 (mod 4) with 2n+1 prime.
It is not known whether there are infinitely many Lucasian primes.

Question:
Are there pseudoprimes m == 3 (mod 4) such that 2m+1 is a pseudoprime?

There only 3 known pseudoprimes m such that 2m+1 is a pseudoprime:
9890881, 23456248059221, 96076792050570581 (see A303447),
but all the three have m == 1 (mod 4).
[Amiram Eldar]

Best regards,

Thomas Ordowski
____________________
https://oeis.org/A002515
https://oeis.org/A081858
https://oeis.org/A001567
https://oeis.org/A303447

```