View source for Distribution of power residues and non-residues

The distribution among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335201.png" /> of those values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335202.png" /> for which the congruence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335203.png" /></td> </tr></table>

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335204.png" />, is solvable (or unsolvable) in integers. Questions on the distribution of power residues and non-residues have been studied most fully in the case modulo a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335205.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335206.png" />. Then the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335207.png" /> is solvable for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335208.png" /> values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d0335209.png" /> in the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352010.png" /> and unsolvable for the remaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352011.png" /> values (see [[Two-term congruence|Two-term congruence]]). However, comparatively little is known about how these values are distributed among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352012.png" />.

The first results about the distribution of power residues were obtained by C.F. Gauss (see [[#References|[1]]]) in 1796. From that time until the work of I.M. Vinogradov only isolated special results were obtained on questions concerning the distribution of power residues and non-residues. In 1915, Vinogradov (see [[#References|[2]]]) proved a series of general results about the distribution of power residues and non-residues, and about primitive roots (cf. [[Primitive root|Primitive root]]) modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352013.png" /> among the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352014.png" />. In particular, he obtained the bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352015.png" /></td> </tr></table>

for the least quadratic non-residue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352016.png" />, and the bound

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352017.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352018.png" /> is the number of distinct prime divisors of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352019.png" />, for the least primitive root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352020.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352021.png" />.

In addition, he made a number of conjectures on the distribution of quadratic residues and non-residues (see [[Vinogradov hypotheses|Vinogradov hypotheses]]) which stimulated a series of investigations in this area. Thus, Yu.V. Linnik [[#References|[3]]] proved that for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352022.png" />, the number of prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352023.png" /> in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352024.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352025.png" /> does not exceed a certain constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352026.png" />, depending only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352027.png" />. Thus, the prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352028.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352029.png" />, if they exist at all, are met only very rarely. Another significant step in the work on Vinogradov's conjectures was the theorem of D.A. Burgess [[#References|[4]]]: For any fixed sufficiently small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352030.png" />, the maximal distance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352031.png" /> between neighbouring quadratic non-residues satisfies the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352032.png" /></td> </tr></table>

In particular, one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352033.png" /></td> </tr></table>

In these inequalities, the constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352035.png" /> depend only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352036.png" /> and not on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352037.png" />. The proof of Burgess' theorem is very complicated; it is based on the Hasse–Weil theorem on the number of solutions of the hyper-elliptic congruence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033520/d03352038.png" /></td> </tr></table>

the proof of which requires techniques of abstract algebraic geometry. For a simple account of Burgess' theorem see [[#References|[5]]], [[#References|[6]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> C.F. Gauss, "Untersuchungen über höhere Arithmetik" , A. Maser (1889) (Translated from Latin) {{MR|0188045}} {{ZBL|21.0166.04}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) {{MR|0807530}} {{ZBL|0577.01049}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> Yu.V. Linnik, ''Dokl. Akad. Nauk SSSR'' , '''36''' (1942) pp. 131</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> D.A. Burgess, "The distribution of quadratic residues and non-residues" ''Mathematika'' , '''4''' : 8 (1957) pp. 106–112 {{MR|0093504}} {{ZBL|0081.27101}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> S.A. Stepanov, "Constructive methods in the theory of equations over finite fields" ''Proc. Steklov Inst. Math.'' , '''132''' (1975) pp. 271–281 ''Trudy Mat. Inst. Steklov.'' , '''132''' (1973) pp. 237–246 {{MR|0337976}} {{ZBL|}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> A.A. Karatsuba, "Character sums and primitive roots in finite fields" ''Soviet Math.-Dokl.'' , '''9''' : 3 (1968) pp. 755–757 ''Dokl. Akad. Nauk SSSR'' , '''180''' : 6 (1968) pp. 1287–1289 {{MR|}} {{ZBL|0182.37501}} </TD></TR></table>