cp's OEIS Frontend

Same as primes p such that if q is the smallest positive quadratic nonresidue mod p, then either q == 0 mod p or q^k == 1 mod p for some positive integer k < p-1.

A primitive root of an odd prime p is always a quadratic nonresidue mod p. (Proof. If g == x^2 mod p, then g^((p-1)/2) == x^(p-1) == 1 mod p, and so g is not a primitive root of p.) But a quadratic nonresidue mod p may or may not be a primitive root of p.

Supersequence of A047936 = primes whose smallest positive primitive root is not prime. (Proof. If p is not in A222717, then the smallest positive quadratic nonresidue of p is a primitive root g. Since the smallest positive quadratic nonresidue is always a prime, g is prime. But since all primitive roots are quadratic nonresidues, g is the smallest positive primitive root of p. Hence p is not in A047936.)

See A001918 (least positive primitive root of the n-th prime) and A053760 (smallest positive quadratic nonresidue of the n-th prime) for references and additional comments and links.

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?

The same primes without repetitions are listed in A147970.

a(n) <= min{A002223(n), A002224(n)}. What is the smallest n for which this inequality is strict?

By definition, a(n) == 1, 7 (mod 8), so a(n) = min{A002223(n), A002224(n)}. - Jianing Song, Feb 18 2019

See the complementary sequence A222717 for comments.

Proth's theorem asserts that p=1+k*2^m (with odd k < 2^m) is prime if there exists b such that b^((p-1)/2) == -1 (mod n). This sequence lists the smallest b which certifies primality of A080076(n) via this relation.

For n > 3, a(n) is an odd prime. - Thomas Ordowski, Apr 23 2019

For n > 0, a(n) = n if and only if 2n+1 is prime.

Note that a(n) < n if and only if 2n+1 is composite.

Conjecture: if 2n+1 is an absolute Euler pseudoprime, then a(n) = 0.

Subset of A053760 corresponding to p == 1 (mod 4).

A002144(n) = p is a sum of two integer squares (Fermat): p = a^2 + b^2. To find a and b, calculate gcd(p, A330406(n)^((p-1)/4)+i) = a + bi in the Gaussian integers.

This list was computed by S. Saidi.

From Travis Scott, Oct 04 2022: (Start)

These are also the p whose (phi/3)-th power residues have minimal bases at {1,2,3} (see under Example). Such covers {1

a(n)-> {1,2,3}(n) = 7, 37, 139, 163, 181, 241, ... ~ (9*n)*log(n)

{1,2,4}(n) = 13, 19, 61, 67, 73, 79, ... ~ (9*n/2)*log(n)

{1,3,5}(n) = 31, 223, 229, 277, 283, 397, ... ~ (27*n)*log(n)

{1,3,7}(n) = 43, 433, 457, 691, 1069, 1471, ... ~ (81*n/2)*log(n)

{1,3,9}(n) = 109, 127, 157, 601, 733, 739, ... ~ (81*n/4)*log(n)

{1,5,7}(n) = 307, 919, 1093, 2179, 2251, 3181, ... ~ (81*n)*log(n)

Note that the k-th q value takes A054272(k) x values and that a(n) = A040034(n) \ {1,2,4}(n). Following a result of Erdős (cf. A053760, A098990) the asymptotic means for q and x are Sum_{n>=1} prime(n)*2/3^n = 2.69463670741804726229622... and Sum_{n>=1} Sum_{prime(n) < k prime < prime(n)^2 OR k = prime(n)^2} D(prime(n),k)*k = 5.69767191389790422108748...

Subsequence of A040034 (2 is not a cubic residue modulo p) such that 3 is neither a residue nor in the same cubic power class as 2. (End)