A307798 The "residue" pseudoprimes: odd composite numbers n such that q(n)^((n-1)/2) == 1 (mod n), where base q(n) is the smallest prime quadratic residue modulo n.

121, 561, 1105, 1541, 1729, 1905, 2465, 4033, 5611, 8321, 8481, 10585, 15709, 15841, 16297, 18705, 18721, 19345, 25761, 28009, 29341, 30121, 31697, 33153, 34945, 42799, 44173, 46657, 49141, 52633, 55969, 62745, 63973, 65077, 69781, 75361, 76627, 79381, 82513, 85489, 88573, 90241, 102311

Offset

1,1

Comments

As is well known, for an odd prime p, a prime q is a quadratic residue modulo p if and only if q^((p-1)/2) == 1 (mod p). Hence the above definition of these pseudoprimes.

Such pseudoprimes n which are both "residue" and "non-residue", obviously to different bases q(n) and b(n), are particularly interesting: 29341, 49141, 1251949, 1373653, 2284453, ... These five numbers are in A244626.

Note that the absolute Euler pseudoprimes 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. The absolute Euler-Jacobi pseudoprimes do not exist.

Links

Table of n, a(n) for n=1..43.

Example

3^((121-1)/2) == 1 (mod 121), 2^((561-1)/2) == 1 (mod 561), ...

Mathematica

q[n_] := Module[{p = 2, pn = Prime[n]}, While[JacobiSymbol[p, pn] != 1, p = NextPrime[p]]; p]; aQ[n_] := CompositeQ[n] && PowerMod[q[n], (n - 1)/2, n] == 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 29 2019 *)

Crossrefs

Cf. A002997, A033181, A306530, A307767 (the "non-residue" pseudoprimes).

Sequence in context: A017654 A183448 A296127 * A204034 A183885 A036306

Adjacent sequences: A307795 A307796 A307797 * A307799 A307800 A307801

Keyword

nonn

Author

Thomas Ordowski, Apr 29 2019

Extensions

More terms from Amiram Eldar, Apr 29 2019

Status

approved