cp's OEIS Frontend

Pomerance et al. gave the terms a(3)-a(10). Pinch gave the terms a(4)-a(13), but a(13)=124882 was wrong. He later calculated the correct value, which appears in Guy's book. - Amiram Eldar, Nov 08 2019

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

Previous name was "Terms of A047713 that are congruent to +-1 mod 8".

Complement of (A244626 union A244628) with respect to A047713. - Jianing Song, Sep 18 2018

Odd composite k with gcd(k,3) = 1 and 3^((k-1)/2) == (3,k) (mod k) where (.,.) is the Jacobi symbol. - R. J. Mathar, Jul 15 2012

The base 5 Euler-Jacobi pseudoprimes are 781, 1541, 1729, 5461, 5611, 6601, 7449, ... - R. J. Mathar, Jul 15 2012 [Typo fixed; this is A375914. - Jianing Song, Sep 02 2024]

These numbers n have the property that, for each prime divisor p, p-1 divides (n-1)/2. E.g., 2465 = 5*17*29; 1232/4 = 308; 1232/16 = 77; 1232/28 = 44. - Karsten Meyer, Nov 08 2005

All these numbers are Carmichael numbers (A002997). - Daniel Lignon, Sep 12 2015

These are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. Note: the absolute Euler-Jacobi pseudoprimes do not exist. Theorem: if an absolute Euler pseudoprime n is a Proth number, then b^((n-1)/2) == 1 for every b coprime to n; by Proth's theorem. Such numbers are 1729, 8355841, 40280065, 53282340865, ...; for example, 1729 = 27*2^6 + 1 with 27 < 2^6. However, it seems that all absolute Euler pseudoprimes n satisfy the stronger congruence b^((n-1)/2) == 1 (mod n) for every b coprime to n, as evidenced by the modified Korselt's criterion (see the first comment). It should be noted that these are odd numbers n such that Carmichael's lambda(n) divides (n-1)/2. Also, these are odd numbers n > 1 coprime to Sum_{k=1..n-1} k^{(n-1)/2}. - Amiram Eldar and Thomas Ordowski, Apr 29 2019

Carmichael numbers k such that (p-1)|(k-1)/2 for each prime p|k. These are odd composite numbers k with half (the maximal possible fraction) of the numbers 1 <= b < k coprime to k that are bases in which k is an Euler-Jacobi pseudoprime, i.e. A329726((k-1)/2)/phi(k) = 1/2. - Amiram Eldar, Nov 20 2019

By Karsten Meyer's and Amiram Eldar's comment, this sequence is numbers k > 1 such that 2*psi(k) | (k-1), where psi = A002322. This means that if k is a term in this sequence, then we actually have a^((k-1)/2) == 1 (mod k) for every a coprime to k. - Jianing Song, Sep 03 2024

All terms are composite because for odd primes p we always have 2^((p-1)/2) == (2/p) = A091337(p) (mod p).

Note that if k is odd and b^((k-1)/2) == -(b/k) (mod k), then taking Jacobi symbol modulo k (which depends only on the remainder modulo k) yields (b/k)^((k-1)/2) = -(b/k), or (b/k)^((k+1)/2) = -1. This implies that (k+1)/2 is odd, so k == 1 (mod 4). Moreover, if k > 1, then (b/k) = -1 (see the Math Stack Exchange link below), so b^((k-1)/2) == 1 (mod k). In particular, this sequence is equivalent to "numbers k == 5 (mod 8) such that 2^((k-1)/2) == 1 (mod k)". [Comment rewritten by Jianing Song, Sep 07 2024]

Also numbers k in A001567 and congruent to 5 modulo 8 such that k - 1 divided by the multiplicative order of 2 modulo k is an even number.

Euler pseudoprimes (A006970) that are not Euler-Jacobi pseudoprimes (A047713). - Amiram Eldar, Oct 28 2019

Note that if k is odd and b^((k-1)/2) == -(b/k) (mod k), then taking Jacobi symbol modulo k (which depends only on the remainder modulo k) yields (b/k)^((k-1)/2) = -(b/k), or (b/k)^((k+1)/2) = -1. This implies that (k+1)/2 is odd, so k == 1 (mod 4). Moreover, if k > 1, then (b/k) = -1 (see the Math Stack Exchange link below), so b^((k-1)/2) == 1 (mod k). In particular, this sequence is equivalent to "numbers k == 5 (mod 12) such that 3^((k-1)/2) == 1 (mod k)". [Comment rewritten by Jianing Song, Sep 07 2024]

Note that if k is odd and b^((k-1)/2) == -(b/k) (mod k), then taking Jacobi symbol modulo k (which depends only on the remainder modulo k) yields (b/k)^((k-1)/2) = -(b/k), or (b/k)^((k+1)/2) = -1. This implies that (k+1)/2 is odd, so k == 1 (mod 4). Moreover, if k > 1, then (b/k) = -1 (see the Math Stack Exchange link below), so b^((k-1)/2) == 1 (mod k). In particular, this sequence is equivalent to "numbers k == 13, 17 (mod 20) such that 5^((k-1)/2) == 1 (mod k)". [Comment rewritten by Jianing Song, Sep 07 2024]