login
Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.
24

%I #76 Aug 13 2024 05:05:16

%S 2,2,2,3,2,2,3,2,5,2,3,2,3,2,5,2,2,2,2,7,5,3,2,3,5,2,3,2,2,3,3,2,3,2,

%T 2,3,2,2,5,2,2,2,7,5,2,3,2,3,2,2,3,7,7,2,3,5,2,3,2,3,2,2,2,11,5,2,2,5,

%U 2,2,3,7,3,2,2,5,2,2,3,7,2,2,7,5,3,2,3,5,2,3,2,13,3,2,2,5,2,3,2,2,2,2,2

%N Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.

%C Assuming the Generalized Riemann Hypothesis, Montgomery proved a(n) << (log p(n))^2, meaning that there is a constant c such that |a(n)| <= c*(log p(n))^2. - _Jonathan Vos Post_, Jan 06 2007

%C a(n) < 1 + sqrt(p), where p is the n-th prime (Theorem 3.9 in Niven, Zuckerman, and Montgomery). - _Jonathan Sondow_, May 13 2010

%C Treviño proves that a(n) < 1.1 p^(1/4) log p for n > 2 where p is the n-th prime. - _Charles R Greathouse IV_, Dec 06 2012

%C a(n) is always a prime, because if x*y is a nonresidue, then x or y must also be a nonresidue. - _Jonathan Sondow_, May 02 2013

%C a(n) is the smallest prime q such that the congruence x^2 == q (mod p) has no solution 0 < x < p, where p = prime(n). For n > 1, a(n) is the smallest base b such that b^((p-1)/2) == -1 (mod p), where odd p = prime(n). - _Thomas Ordowski_, Apr 24 2019

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 94-98.

%D Hugh L. Montgomery, Topics in Multiplicative Number Theory, 3rd ed., Lecture Notes in Mathematics, Vol. 227 (1971), MR 49:2616.

%D Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991, p. 147.

%D Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag 1996; Math. Rev. 96k:11112.

%H T. D. Noe, <a href="/A053760/b053760.txt">Table of n, a(n) for n = 1..10000</a>

%H Robert Baillie and Samuel S. Wagstaff, <a href="https://doi.org/10.1090/S0025-5718-1980-0583518-6">Lucas pseudoprimes</a>, Mathematics of Computation, Vol. 35, No. 152 (1980), pp. 1391-1417, Math. Rev. 81j:10005, <a href="http://mpqs.free.fr/LucasPseudoprimes.pdf">alternative link</a>.

%H Paul Erdős, <a href="http://www.renyi.hu/~p_erdos/1961-23.pdf">Remarks on number theory. I.</a>, Mat. Lapok, Vol. 12 (1961), pp. 10-17; Math. Rev. 26 #2410.

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/hdmrd/jacobi.html">Quadratic Residues</a> [Broken link]

%H Steven R. Finch, <a href="http://web.archive.org/web/20010208112444/http://www.mathsoft.com/asolve/constant/hdmrd/jacobi.html">Quadratic Residues</a> [From the Wayback machine]

%H Keith Matthews, <a href="http://www.numbertheory.org/php/leastqnr.html">Finding n(p), the least quadratic non-residue (mod p)</a>

%H Enrique Treviño, <a href="https://doi.org/10.1016/j.jnt.2014.10.019">The least k-th power non-residue</a>, Journal of Number Theory, Vol. 149 (2015),pp. 201-224, <a href="http://campus.lakeforest.edu/trevino/LeastNonResidue.pdf">alternative link</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/QuadraticNonresidue.html">Quadratic Nonresidue</a>.

%F a(n) = A020649(prime(n)) for n > 1. - _Thomas Ordowski_, Apr 24 2019

%F Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A098990 (Erdős, 1961). - _Amiram Eldar_, Oct 29 2020

%e The 5th prime is 11, and the positive quadratic residues mod 11 are 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 5 and 5^2 = 3. Since 2 is missing, a(5) = 2.

%e The only positive quadratic redidue mod 2 is 1, so a(1)=2.

%t Table[ p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 100}] (* _Jonathan Sondow_, Mar 03 2013 *)

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

%o A053760(n)={local(r,m);r=0;m=0;while(r==0,m=m+1;if(!residue(m,prime(n)),r=1));m} \\ Michael B. Porter, May 02 2010

%o (PARI) qnr(p)=my(m);while(1,if(!issquare(Mod(m++,p)),return(m)))

%o a(n)=if(n>1,qnr(prime(n)),2) \\ _Charles R Greathouse IV_, Feb 27 2013

%Y Cf. A000229, A020649, A098990.

%K nonn

%O 1,1

%A _Steven Finch_, Apr 05 2000

%E More terms from _James A. Sellers_, Apr 08 2000