A244628 Composite numbers n such that n == 3 (mod 8) and 2^((n-1)/2) == -1 (mod n).

476971, 877099, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 3090091, 3116107, 5256091, 5919187, 7883731, 9371251, 11081459, 11541307, 12263131, 13057787, 13338371, 15976747, 17134043, 18740971, 19404139, 20261251, 21623659, 22075579, 24214051

Offset: 1

Author

Gary Detlefs, Jul 02 2014

Keywords

• nonn

Comments

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

Conjecture 1: if p is a 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 modified primality test has far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a much higher probability of success. The number of pseudoprimes up to 10^k for the two tests are:

10^3 0 0

10^4 0 2

10^5 0 5

10^6 2 14

10^7 16 48

This sequence appears to be a subset of the composites in A175865.

The n mod 8 = 3 pseudoprimes are much rarer than the n mod 8 = 5 pseudoprimes. There are 16 terms < 10^7. If the additional constraints 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 are added, no terms remain.

Number of terms < 10^k: 0, 0, 0, 0, 0, 2, 16, 50, 132, ..., . - Robert G. Wilson v, Jul 21 2014

Number of terms < 10^k for k=5..15: 0, 2, 16, 50, 132, 341, 876, 2330, 6234, 16625, 44885. - Jens Kruse Andersen, Jul 27 2014

It appears that the terms of the sequence are also the composite numbers of A294912. - Hilko Koning, Dec 05 2019

Also composite numbers 2k+1 with k odd such that 2k+1 | 2^k+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 (first 132 terms from Robert G. Wilson v)

Crossrefs

Cf. A003629, A070179, A175865.

Programs

Maple

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

Mathematica

fQ[n_] := !PrimeQ@ n && PowerMod[2, (n - 1)/2, n] == n - 1; k = 3; lst = {}; While[k < 10^8, If[fQ@ k, AppendTo[lst, k]]; k += 8]; lst (* Robert G. Wilson v, Jul 21 2014 *)