login
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.
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
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.
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
KEYWORD
nonn
AUTHOR
Thomas Ordowski, Apr 29 2019
EXTENSIONS
More terms from Amiram Eldar, Apr 29 2019
STATUS
approved