

A307798


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


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^((p1)/2) == 1 (mod p). Hence the above definition of these pseudoprimes.
Such pseudoprimes n which are both "residue" and "nonresidue", 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^((n1)/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^((n1)/2) == 1 (mod n) for every base b that is a quadratic nonresidue modulo n and coprime to n. The absolute EulerJacobi pseudoprimes do not exist.


LINKS



EXAMPLE

3^((1211)/2) == 1 (mod 121), 2^((5611)/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



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



