[seqfan] Re: The nonresidue pseudoprimes

[Tomasz Ordowski]

P.S. I also noticed that

(*) 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;
(***) a "non-residue" pseudoprime n is not a Proth number, so n = k2^m+1
with odd k > 2^m.

Thomas Ordowski

pt., 26 kwi 2019 o 11:27 Tomasz Ordowski <tomaszordowski at gmail.com>
napisał(a):

> Dear SeqFans!
>
> 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(p) is a prime.
>
> Let's define related pseudoprimes:
> Odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n),
> where base b(n) is the smallest quadratic non-residue modulo n.
> I noticed that b(n) is always a prime.
>
> Here are the "non-residue" pseudoprimes:
> 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,
> 1811573,  1907851, 1987021, 2004403, ... [Data from Amiram Eldar].
>
> Problem: Are there infinitely many such numbers?
>
> Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as
> above.
> This is obvious for odd prime numbers n; is it for odd composite numbers
> n?
> If so, then all composites of the form 2^((n-1)/2) == -1 (mod n) are in
> this set.
>
> It seems that, for defined pseudoprimes n (similar to the odd primes p),
> b(n) is the smallest base b such b^((n-1)/2) == -1 (mod n),
> although this is not required by their definition.
>
> Let a(q) is the smallest odd composite k such that q^((k-1)/2) == -1 (mod
> k)
> and the smallest quadratic non-residue b(k) = q prime.
>
> q, a(q):
> =====
> 2, 3277;
> 3, 3281;
> 5, 121463;
> 7, 491209;
> 11, 11530801;
> 13, 512330281;
> ... [Amiram Eldar].
>
> Cf. https://oeis.org/A000229 (such the smallest odd primes).
>
> Are such pseudoprimes known in the number theory?
>
> I am asking for comments.
>
> Best regards,
>
> Thomas Ordowski
> ________________________________________
> https://oeis.org/history/view?seq=A020649&v=19
> https://oeis.org/history/view?seq=A053760&v=62
>
>