# [seqfan] Exact "non-residue" and "residue" pseudoprimes

Tomasz Ordowski tomaszordowski at gmail.com
Mon May 6 08:51:45 CEST 2019

Dear SeqFans,

I defined the following two sequences of special pseudoprimes:
_______________
The first sequence:
a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1
(mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

a(n) = 3277, 5173601, 2329584217, 188985961 for n = 1, 2, 3, 4. Is this
sequence infinite?

Some upper-bounds for the next five terms:
a(5) <= 32203213602841,
a(6) <= 323346556958041,
a(7) <= 2528509579568281,
a(8) <= 5189206896360728641,
a(9) <= 12155831039329417441
[Daniel Suteu].

Conjecture: The smallest quadratic non-residue modulo a(n) is prime(n):
A020649(a(n)) = prime(n). See https://oeis.org/A020649
Such a term a(n) is an exact "non-residue" pseudoprime* (see below).
__________________
The second sequence:
b(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == 1 (mod
k) and q^((k-1)/2) == -1 (mod k) for every prime q < prime(n).

b(n) = 341, 29341,48354810571 for n = 1, 2, 3.  Is this sequence infinite?

Some upper-bounds for the next four terms:
b(4) <= 493813961816587,
b(5) <= 32398013051587,
b(6) <= 35141256146761030267,
b(7) <= 4951782572086917319747
[Daniel Suteu].

Conjecture: The smallest prime quadratic residue modulo b(n) is prime(n):
Such a term a(n)  is an exact "residue" pseudoprime** (see  below).
____________
The prototypes of the appropriate sequences of primes, below.

Computational problem: Find more terms of these sequences.

I am waiting for comments and calculation results.

Best regards,

Thomas Ordowski & Amiram Eldar
___________________________________________
Cf. https://oeis.org/history/view?seq=A000229&v=69 (see the last comment).

Let b(n) be the smallest prime p = prime(k) > prime(n) such that A306530(k)
= prime(n).
7, 11, 19, 53, 43, 173, 67, 2477, 8803, 9173, 32323, 37123, 163, 74093,
170957, 360293, 679733, 2404147, 2004917, 69009533, 51599563, 155757067,
96295483, 146161723, 1408126003, 3519879677, 2050312613, 3341091163,
78864114883, 65315700413, 1728061733, 9447241877, ...
This is a sequence analogous to A000229, but for smallest prime quadratic
residue modulo p.
Note that b(n) is the smallest odd number m > prime(n) such that
prime(n)^((m-1)/2) == 1 (mod m) and q^((m-1)/2) == -1 (mod m) for every
prime q < prime(n).
Such m is always an odd prime p.

(*) Generally, the exact "non-residue" pseudoprimes, I defined:
Odd composite numbers n such that p^((n-1)/2) == -1 (mod n) and b^((n-1)/2)
== 1 (mod n) for every natural b < p, where p is a prime.
Conjecture: If n is such a pseudoprime, then the smallest non-residue
modulo n is p: A020649(n) = p, where p as above.

(**) Generally, the exact "residue" pseudoprimes, I defined:
Odd composite numbers n such that p^((n-1)/2) == 1 (mod n) and q^((n-1)/2)
== -1 (mod n) for every prime base q < p, where p is a prime.
Conjecture: If n is such a pseudoprime, then the smallest prime quadratic
residue modulo n is p, where p as above.
_______