A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 489997, 800605, 838861, 873181, 1004653, 1251949, 1373653, 1509709, 1678541, 1811573, 1987021, 2269093, 2284453, 2387797, 2746477, 2909197, 3400013, 3429037, 3539101, 3605429, 4360621, 4502485, 5590621, 5599765

Offset

1,1

Comments

This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:

Conjecture 1: if p is an odd prime congruent to {3,5} (mod 8) then 2^((p-1)/2) mod p = p-1.

This conjecture has been tested to 10^8.

This criterion produces far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a higher probability of success. The number of pseudoprimes for the two tests up to 10^k are:

10^5 5 26 19.23%

10^6 13 78 16.66%

10^7 40 228 17.54%

There are 40 terms < 10^7. If an additional constraint 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 is added, only 4 terms remain: (29341, 314821, 873181, 9863461).

This sequence appears to be a subset of A175865, A001262, A047713, A020230.

Number of terms below 10^k for k = 5..15: 5, 13, 40, 132, 369, 975, 2534, 6592, 17403, 45801, 122473. The corresponding numbers for 2^(n-1) mod n = 1: 26, 78, 228, 637, 1718, 4505, 11645, 29902, 76587, 197455, 513601. - Jens Kruse Andersen, Jul 13 2014

Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+1. - Hilko Koning, Jan 27 2022

Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k. Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - Hilko Koning, Feb 04 2022

Links

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

Maple

for n from 5 to 10^7 by 8 do if 2^((n-1)/2) mod n = n-1 and not isprime(n) then print(n) fi od;

Crossrefs

Cf. A001567, A003629, A070179.

Sequence in context: A116460 A245482 A356638 * A270204 A293626 A152506

Adjacent sequences: A244623 A244624 A244625 * A244627 A244628 A244629

Keyword

nonn

Author

Gary Detlefs, Jul 02 2014

Extensions

a(18) corrected by Jens Kruse Andersen, Jul 13 2014

Status

approved