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!)
A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n). 3
3277, 3281, 29341, 49141, 80581, 88357, 104653, 121463, 196093, 314821, 320167, 458989, 476971, 489997, 491209, 721801, 800605, 838861, 873181, 877099, 973241, 1004653, 1251949, 1268551, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1590751, 1678541, 1809697 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.

Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.

It seems that, for defined pseudoprimes n (similar to the odd primes p),

b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.

Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.

Problem: are there infinitely many such numbers?

LINKS

Table of n, a(n) for n=1..35.

EXAMPLE

2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...

MATHEMATICA

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 27 2019 *)

CROSSREFS

Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.

Sequence in context: A237085 A260410 A223430 * A307809 A141629 A116460

Adjacent sequences:  A307764 A307765 A307766 * A307768 A307769 A307770

KEYWORD

nonn

AUTHOR

Thomas Ordowski, Apr 27 2019

EXTENSIONS

More terms from Amiram Eldar, Apr 27 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 July 11 15:58 EDT 2020. Contains 335626 sequences. (Running on oeis4.)