[seqfan] The nonresidue pseudoprimes
Tomasz Ordowski
tomaszordowski at gmail.com
Fri Apr 26 11:27:09 CEST 2019
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
More information about the SeqFan
mailing list