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, 1297, 1303, 1321, 1399, 1429, 1459, 1471, 1489, 1543, 1559, 1579, 1597, 1613, 1627, 1657, 1699, 1709, 1723, 1753, 1759, 1783, 1789, 1811, 1871, 1873, 1879, 1933

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 a 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.

The smallest positive quadratic nonresidue of 2 is 2 itself, and 2 is not a primitive root of 2, so 2 is a member.

NR = (Table[p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 300}]); Select[ Prime[ Range[300]], Mod[ NR[[PrimePi[#]]], #] == 0 || MultiplicativeOrder[ NR[[ PrimePi[#]]], #] < # - 1 &]

approved

editing

reviewed

approved

proposed

reviewed

editing

proposed

allocated for Jonathan SondowPrimes p whose smallest positive quadratic nonresidue is not a primitive root of p.

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, 1297, 1303, 1321, 1399, 1429, 1459, 1471, 1489, 1543, 1559, 1579, 1597, 1613, 1627, 1657, 1699, 1709, 1723, 1753, 1759, 1783, 1789, 1811, 1871, 1873, 1879, 1933

1,1

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

A primitive root of a 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.

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.

<a href="/index/Pri#primes_root">Index entries for primes by primitive root</a>

The smallest positive quadratic nonresidue of 41 is 3, and 3 is not a primitive root of 41, so 41 is a member.

NR = (Table[p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 300}]); Select[ Prime[ Range[300]], MultiplicativeOrder[ NR[[ PrimePi[#]]], #] < # - 1 &]

Cf. A001918, A053760.

allocated

nonn

Jonathan Sondow, Mar 12 2013

approved

editing

allocated for Jonathan Sondow

allocated

approved