[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A222717 revision #14

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
proposed