cp's OEIS Frontend

A020649 Least quadratic nonresidue modulo n (with n >= 3).

%I A020649 #35 Feb 16 2025 08:32:34
%S A020649 2,2,2,2,3,2,2,2,2,2,2,3,2,2,3,2,2,2,2,2,5,2,2,2,2,2,2,2,3,2,2,3,2,2,
%T A020649 2,2,2,2,3,2,2,2,2,5,5,2,3,2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2,2,
%U A020649 7,2,5,2,2,2,2,2,3,2,2,3,2,2,2,2,2,2,3,2,2,2,2,5,2,2,5,3,2,2,2,2,3,2,2,2,2,2,2,2
%N A020649 Least quadratic nonresidue modulo n (with n >= 3).
%C A020649 a(n) is the smallest q such that the congruence x^2 == q (mod n) has no solution 0 <= x < n, for n > 2. Note that a(n) is a prime. If n is an odd prime p, then a(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p), see A053760. - _Thomas Ordowski_, Apr 24 2019
%H A020649 Amiram Eldar, <a href="/A020649/b020649.txt">Table of n, a(n) for n = 3..10000</a>
%H A020649 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticNonresidue.html">Quadratic Nonresidue</a>
%F A020649 a(prime(n)) = A053760(n) for n > 1. - _Thomas Ordowski_, Apr 24 2019
%t A020649 a[n_] := Min @ Complement[Range[n - 1], Mod[Range[n/2]^2, n]]; Table[a[n], {n, 3, 110}] (* _Amiram Eldar_, Oct 29 2020 *)
%o A020649 (PARI) residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
%o A020649 A020649(n)={local(r,m);r=0;m=0;while(r==0,m=m+1;if(!residue(m,n),r=1));m} \\ _Michael B. Porter_, Apr 30 2010
%Y A020649 Cf. A053760.
%K A020649 nonn
%O A020649 3,1
%A A020649 _David W. Wilson_