A020649 - OEIS

A020649

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

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, 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, 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

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,1

COMMENTS

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

LINKS

Amiram Eldar, Table of n, a(n) for n = 3..10000

Eric Weisstein's World of Mathematics, Quadratic Nonresidue

FORMULA

a(prime(n)) = A053760(n) for n > 1. - Thomas Ordowski, Apr 24 2019

MATHEMATICA

a[n_] := Min @ Complement[Range[n - 1], Mod[Range[n/2]^2, n]]; Table[a[n], {n, 3, 110}] (* Amiram Eldar, Oct 29 2020 *)

PROG

(PARI) residue(n, m)={local(r); r=0; for(i=0, floor(m/2), if(i^2%m==n, r=1)); r}

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

CROSSREFS

Cf. A053760.