|
%I #14 Jul 20 2019 17:38:28
%S 121,561,1105,1541,1729,1905,2465,4033,5611,8321,8481,10585,15709,
%T 15841,16297,18705,18721,19345,25761,28009,29341,30121,31697,33153,
%U 34945,42799,44173,46657,49141,52633,55969,62745,63973,65077,69781,75361,76627,79381,82513,85489,88573,90241,102311
%N 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.
%C 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.
%C 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.
%C 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.
%e 3^((121-1)/2) == 1 (mod 121), 2^((561-1)/2) == 1 (mod 561), ...
%t 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 *)
%Y Cf. A002997, A033181, A306530, A307767 (the "non-residue" pseudoprimes).
%K nonn
%O 1,1
%A _Thomas Ordowski_, Apr 29 2019
%E More terms from _Amiram Eldar_, Apr 29 2019
|
