login
A222717
Primes p whose smallest positive quadratic nonresidue is not a primitive root of p.
3
2, 41, 43, 103, 109, 151, 157, 191, 229, 251, 271, 277, 283, 307, 311, 313, 331, 337, 367, 397, 409, 439, 457, 499, 571, 643, 683, 691, 727, 733, 739, 761, 769, 811, 911, 919, 967, 971, 991, 997, 1013, 1021, 1031, 1051, 1069, 1093, 1151, 1163, 1181, 1289
OFFSET
1,1
COMMENTS
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.
EXAMPLE
The smallest positive quadratic nonresidue of 2 is 2 itself, and 2 is not a primitive root of 2, so 2 is a member.
The smallest positive quadratic nonresidue of 41 is 3, and 3 is not a primitive root of 41, so 41 is a member.
MATHEMATICA
nn = 300; NR = (Table[p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, nn}]); Select[ Prime[ Range[nn]], Mod[ NR[[PrimePi[#]]], #] == 0 || MultiplicativeOrder[ NR[[PrimePi[#]]], #] < # - 1 &]
CROSSREFS
KEYWORD
nonn
AUTHOR
Jonathan Sondow, Mar 12 2013
STATUS
approved