|
|
A053760
|
|
Smallest positive quadratic nonresidue modulo p, where p is the n-th prime.
|
|
24
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
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
|
|
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
|
|
|
FORMULA
|
Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A098990 (Erdős, 1961). - Amiram Eldar, Oct 29 2020
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
Table[ p = Prime[n]; First[ Select[ Range[p], JacobiSymbol[#, p] != 1 &]], {n, 1, 100}] (* Jonathan Sondow, Mar 03 2013 *)
|
|
PROG
|
(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)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|