cp's OEIS Frontend

A222717 Primes p whose smallest positive quadratic nonresidue is not a primitive root of p.

%I A222717 #16 Mar 14 2013 12:06:44
%S A222717 2,41,43,103,109,151,157,191,229,251,271,277,283,307,311,313,331,337,
%T A222717 367,397,409,439,457,499,571,643,683,691,727,733,739,761,769,811,911,
%U A222717 919,967,971,991,997,1013,1021,1031,1051,1069,1093,1151,1163,1181,1289
%N A222717 Primes p whose smallest positive quadratic nonresidue is not a primitive root of p.
%C A222717 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.
%C A222717 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.
%C A222717 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.)
%C A222717 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.
%H A222717 <a href="/index/Pri#primes_root">Index entries for primes by primitive root</a>
%e A222717 The smallest positive quadratic nonresidue of 2 is 2 itself, and 2 is not a primitive root of 2, so 2 is a member.
%e A222717 The smallest positive quadratic nonresidue of 41 is 3, and 3 is not a primitive root of 41, so 41 is a member.
%t A222717 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 &]
%Y A222717 Cf. A001918, A047936, A053760, A223036.
%K A222717 nonn
%O A222717 1,1
%A A222717 _Jonathan Sondow_, Mar 12 2013