login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (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^((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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 2 08:23 EDT 2020. Contains 334767 sequences. (Running on oeis4.)