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

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

Offset: 1

Author

Steven Finch, Apr 05 2000

Keywords

• nonn

Comments

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

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

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

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

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

Examples

			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.
The only positive quadratic redidue mod 2 is 1, so a(1)=2.
		

References

• Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 94-98.
• Hugh L. Montgomery, Topics in Multiplicative Number Theory, 3rd ed., Lecture Notes in Mathematics, Vol. 227 (1971), MR 49:2616.
• 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.
• Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag 1996; Math. Rev. 96k:11112.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Robert Baillie and Samuel S. Wagstaff, Lucas pseudoprimes, Mathematics of Computation, Vol. 35, No. 152 (1980), pp. 1391-1417, Math. Rev. 81j:10005, alternative link.
• Paul Erdős, Remarks on number theory. I., Mat. Lapok, Vol. 12 (1961), pp. 10-17; Math. Rev. 26 #2410.
• Steven R. Finch, Quadratic Residues [Broken link]
• Steven R. Finch, Quadratic Residues [From the Wayback machine]
• Keith Matthews, Finding n(p), the least quadratic non-residue (mod p)
• Enrique Treviño, The least k-th power non-residue, Journal of Number Theory, Vol. 149 (2015),pp. 201-224, alternative link.
• Eric Weisstein's World of Mathematics, Quadratic Nonresidue.

Crossrefs

Cf. A000229, A020649, A098990.

Programs

Mathematica

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

PARI

residue(n,m)={local(r);r=0;for(i=0,floor(m/2),if(i^2%m==n,r=1));r}
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

PARI

qnr(p)=my(m);while(1,if(!issquare(Mod(m++,p)),return(m)))
a(n)=if(n>1,qnr(prime(n)),2) \\ Charles R Greathouse IV, Feb 27 2013

Formula

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

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

Extensions

More terms from James Sellers, Apr 08 2000