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