Editing Quadratic residue (section)

==Distribution of quadratic residues==

Although quadratic residues appear to occur in a rather random pattern modulo ''n'', and this has been exploited in such [[#Applications of quadratic residues|applications]] as [[#Acoustics|acoustics]] and [[#Cryptography|cryptography]], their distribution also exhibits some striking regularities.

Using [[Dirichlet's theorem on arithmetic progressions|Dirichlet's theorem]] on primes in [[arithmetic progression]]s, the [[law of quadratic reciprocity]], and the [[Chinese remainder theorem]] (CRT) it is easy to see that for any ''M'' > 0 there are primes ''p'' such that the numbers 1, 2, ..., ''M'' are all residues modulo ''p''.
<blockquote>For example, if ''p'' ≡ 1 (mod 8), (mod 12), (mod 5) and (mod 28), then by the law of quadratic reciprocity 2, 3, 5, and 7 will all be residues modulo ''p'', and thus all numbers 1&ndash;10 will be. The CRT says that this is the same as ''p'' ≡ 1 (mod 840), and Dirichlet's theorem says there are an infinite number of primes of this form. 2521 is the smallest, and indeed 1<sup>2</sup> ≡ 1, 1046<sup>2</sup> ≡ 2, 123<sup>2</sup> ≡ 3, 2<sup>2</sup> ≡ 4, 643<sup>2</sup> ≡ 5, 87<sup>2</sup> ≡ 6, 668<sup>2</sup> ≡ 7, 429<sup>2</sup> ≡ 8, 3<sup>2</sup> ≡ 9, and 529<sup>2</sup> ≡ 10 (mod 2521).</blockquote>

===Dirichlet's formulas===

The first of these regularities stems from [[Peter Gustav Lejeune Dirichlet]]'s work (in the 1830s) on the [[class number formula|analytic formula]] for the [[Class number (number theory)|class number]] of binary [[quadratic form]]s.<ref>{{harvnb|Davenport|2000|pp=8&ndash;9, 43&ndash;51}}. These are classical results.</ref> Let ''q'' be a prime number, ''s'' a complex variable, and define a [[Dirichlet L-function]] as
:<math>L(s) = \sum_{n=1}^\infty\left(\frac{n}{q}\right)n^{-s}. </math>

Dirichlet showed that if ''q'' ≡ 3 (mod 4), then
:<math>L(1) = -\frac{\pi}{\sqrt q}\sum_{n=1}^{q-1} \frac{n}{q} \left(\frac{n}{q}\right) > 0.</math>

Therefore, in this case (prime ''q'' ≡ 3 (mod 4)), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., ''q'' &minus; 1 is a negative number.
<blockquote>
For example, modulo 11,

:'''1''', 2, '''3''', '''4''', '''5''', 6, 7, 8, '''9''', 10 (residues in '''bold''')

:1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, and the difference is &minus;11. </blockquote>

In fact the difference will always be an odd multiple of ''q'' if ''q'' > 3.<ref>{{harvnb|Davenport|2000|pp=49&ndash;51}}, (conjectured by [[Carl Gustav Jacob Jacobi|Jacobi]], proved by Dirichlet)</ref> In contrast, for prime ''q'' ≡ 1 (mod 4), the sum of the quadratic residues minus the sum of the nonresidues in the range 1, 2, ..., ''q'' &minus; 1 is zero, implying that both sums equal <math>\frac{q(q-1)}{4}</math>.{{cn|date=November 2020}}

Dirichlet also proved that for prime ''q'' ≡ 3 (mod 4),
:<math>L(1) = \frac{\pi}{\left(2-\left(\frac{2}{q}\right)\right)\!\sqrt q}\sum_{n=1}^\frac{q-1}{2}\left(\frac{n}{q}\right) > 0.</math>
This implies that there are more quadratic residues than nonresidues among the numbers 1, 2, ..., (''q'' &minus; 1)/2.

<blockquote>For example, modulo 11 there are four residues less than 6 (namely 1, 3, 4, and 5), but only one nonresidue (2).</blockquote>

An intriguing fact about these two theorems is that all known proofs rely on analysis; no-one has ever published a simple or direct proof of either statement.<ref>{{harvnb|Davenport|2000|p=9}}</ref>

===Law of quadratic reciprocity===

{{Main|quadratic reciprocity}}

If ''p'' and ''q'' are odd primes, then:

((''p'' is a quadratic residue mod ''q'') if and only if (''q'' is a quadratic residue mod ''p'')) if and only if (at least one of ''p'' and ''q'' is congruent to 1 mod 4).

That is:

:<math> \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}</math>

where <math>\left(\frac{p}{q}\right)</math> is the [[Legendre symbol]].

Thus, for numbers ''a'' and odd primes ''p'' that don't divide ''a'':

{|class="wikitable"
!''a''
!''a'' is a quadratic residue mod ''p'' if and only if
!''a''
!''a'' is a quadratic residue mod ''p'' if and only if
|-
|1
|(every prime ''p'')
|−1
|''p'' ≡ 1 (mod 4)
|-
|2
|''p'' ≡ 1, 7 (mod 8)
|−2
|''p'' ≡ 1, 3 (mod 8)
|-
|3
|''p'' ≡ 1, 11 (mod 12)
|−3
|''p'' ≡ 1 (mod 3)
|-
|4
|(every prime ''p'')
|−4
|''p'' ≡ 1 (mod 4)
|-
|5
|''p'' ≡ 1, 4 (mod 5)
|−5
|''p'' ≡ 1, 3, 7, 9 (mod 20)
|-
|6
|''p'' ≡ 1, 5, 19, 23 (mod 24)
|−6
|''p'' ≡ 1, 5, 7, 11 (mod 24)
|-
|7
|''p'' ≡ 1, 3, 9, 19, 25, 27 (mod 28)
|−7
|''p'' ≡ 1, 2, 4 (mod 7)
|-
|8
|''p'' ≡ 1, 7 (mod 8)
|−8
|''p'' ≡ 1, 3 (mod 8)
|-
|9
|(every prime ''p'')
|−9
|''p'' ≡ 1 (mod 4)
|-
|10
|''p'' ≡ 1, 3, 9, 13, 27, 31, 37, 39 (mod 40)
|−10
|''p'' ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
|-
|11
|''p'' ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44)
|−11
|''p'' ≡ 1, 3, 4, 5, 9 (mod 11)
|-
|12
|''p'' ≡ 1, 11 (mod 12)
|−12
|''p'' ≡ 1 (mod 3)
|}

===Pairs of residues and nonresidues===

Modulo a prime ''p'', the number of pairs ''n'', ''n'' + 1 where ''n'' R ''p'' and ''n'' + 1 R ''p'', or ''n'' N ''p'' and ''n'' + 1 R ''p'', etc., are almost equal. More precisely,<ref>Lemmermeyer, p. 29 ex. 1.22; cf pp. 26&ndash;27, Ch. 10</ref><ref>Crandall & Pomerance, ex 2.38, pp 106&ndash;108</ref> let ''p'' be an odd prime. For ''i'', ''j'' = 0, 1 define the sets
:<math>A_{ij}=\left\{k\in\{1,2,\dots,p-2\}: \left(\frac{k}{p}\right)=(-1)^i\land\left(\frac{k+1}{p}\right)=(-1)^j\right\},</math>
and let
:<math>\alpha_{ij} = |A_{ij}|.</math>

That is,
:&alpha;<sub>00</sub> is the number of residues that are followed by a residue,
:&alpha;<sub>01</sub> is the number of residues that are followed by a nonresidue,
:&alpha;<sub>10</sub> is the number of nonresidues that are followed by a residue, and
:&alpha;<sub>11</sub> is the number of nonresidues that are followed by a nonresidue.

Then if ''p'' ≡ 1 (mod 4)

:<math>\alpha_{00} = \frac{p-5}{4},\;\alpha_{01} =\alpha_{10} =\alpha_{11} = \frac{p-1}{4} </math>

and if ''p'' ≡ 3 (mod 4)

:<math>\alpha_{01} = \frac{p+1}{4},\;\alpha_{00} =\alpha_{10} =\alpha_{11} = \frac{p-3}{4}. </math>

<blockquote>For example: (residues in '''bold''')

Modulo 17
:'''1''', '''2''', 3, '''4''', 5, 6, 7, '''8''', '''9''', 10, 11, 12, '''13''', 14, '''15''', '''16'''
::''A''<sub>00</sub> = {1,8,15},
::''A''<sub>01</sub> = {2,4,9,13},
::''A''<sub>10</sub> = {3,7,12,14},
::''A''<sub>11</sub> = {5,6,10,11}.

Modulo 19
:'''1''', 2, 3, '''4''', '''5''', '''6''', '''7''', 8, '''9''', 10, '''11''', 12, 13, 14, 15, '''16''', '''17''', 18
::''A''<sub>00</sub> = {4,5,6,16},
::''A''<sub>01</sub> = {1,7,9,11,17},
::''A''<sub>10</sub> = {3,8,10,15},
::''A''<sub>11</sub> = {2,12,13,14}. </blockquote>

Gauss (1828)<ref>Gauss, ''Theorie der biquadratischen Reste, Erste Abhandlung'' (pp 511&ndash;533 of the ''Untersuchungen über hohere Arithmetik)''</ref> introduced this sort of counting when he proved that if ''p'' ≡ 1 (mod 4) then ''x''<sup>4</sup> ≡ 2 (mod ''p'') can be solved if and only if ''p''&nbsp;=&nbsp;''a''<sup>2</sup>&nbsp;+&nbsp;64&nbsp;''b''<sup>2</sup>.

===The Pólya&ndash;Vinogradov inequality===

The values of <math>(\tfrac{a}{p})</math> for consecutive values of ''a'' mimic a random variable like a [[coin flip]].<ref>Crandall & Pomerance, ex 2.38, pp 106&ndash;108 discuss the similarities and differences. For example, tossing ''n'' coins, it is possible (though unlikely) to get ''n''/2 heads followed by that many tails. V-P inequality rules that out for residues.</ref> Specifically, [[George Pólya|Pólya]] and [[Ivan Matveevich Vinogradov|Vinogradov]] proved<ref>{{harvnb|Davenport|2000|pp=135–137}}, (proof of P&ndash;V, (in fact big-O can be replaced by 2); journal references for Paley, Montgomery, and Schur)</ref> (independently) in 1918 that for any nonprincipal [[Dirichlet character]] χ(''n'') modulo ''q'' and any integers ''M'' and ''N'',

:<math>\left|\sum_{n=M+1}^{M+N}\chi(n)\right| =O\left( \sqrt q \log q\right),</math>

in [[big O notation]]. Setting

:<math> \chi(n) = \left(\frac{n}{q}\right),</math>

this shows that the number of quadratic residues modulo ''q'' in any interval of length ''N'' is

:<math>\frac{1}{2}N + O(\sqrt q\log q).</math>

It is easy<ref>Planet Math: Proof of Pólya&ndash;Vinogradov Inequality in [[#External links|external links]]. The proof is a page long and only requires elementary facts about Gaussian sums</ref> to prove that

:<math> \left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \sqrt q \log q.</math>

In fact,<ref>Pomerance & Crandall, ex 2.38 pp.106&ndash;108. result from T. Cochrane, "On a trigonometric inequality of Vinogradov", ''J. Number Theory'', 27:9&ndash;16, 1987</ref>

:<math> \left| \sum_{n=M+1}^{M+N} \left( \frac{n}{q} \right) \right| < \frac{4}{\pi^2} \sqrt q \log q+0.41\sqrt q +0.61.</math>

[[Hugh Montgomery (mathematician)|Montgomery]] and [[Robert Charles Vaughan (mathematician)|Vaughan]] improved this in 1977, showing that, if the [[generalized Riemann hypothesis]] is true then

:<math>\left|\sum_{n=M+1}^{M+N}\chi(n)\right|=O\left(\sqrt q \log  \log q\right).</math>

This result cannot be substantially improved, for [[Issai Schur|Schur]] had proved in 1918 that

:<math>\max_N \left|\sum_{n=1}^{N}\left(\frac{n}{q}\right)\right|>\frac{1}{2\pi}\sqrt q</math>

and [[Raymond Paley|Paley]] had proved in 1932 that

:<math>\max_N \left|\sum_{n=1}^{N}\left(\frac{d}{n}\right)\right|>\frac{1}{7}\sqrt d \log \log d</math>

for infinitely many ''d'' > 0.

===Least quadratic non-residue===
The least quadratic residue mod ''p'' is clearly 1.  The question of the magnitude of the least quadratic non-residue ''n''(''p'') is more subtle, but it is always prime, with 7 appearing for the first time at 71.

The Pólya–Vinogradov inequality above gives O({{radic|''p''}} log ''p''). 

The best unconditional estimate is ''n''(''p'') ≪ ''p''<sup>θ</sup> for any θ>1/4{{radic|e}}, obtained by estimates of Burgess on [[character sum]]s.<ref name=FI156/> 

Assuming the [[Generalised Riemann hypothesis]], Ankeny obtained ''n''(''p'') ≪ (log ''p'')<sup>2</sup>.<ref>{{cite book | title=Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis | first=Hugh L. | last=Montgomery | author-link=Hugh Montgomery (mathematician) | publisher=[[American Mathematical Society]] | year=1994 | isbn=0-8218-0737-4 | zbl=0814.11001 | page=176 }}</ref> 

[[Linnik]] showed that the number of ''p'' less than ''X'' such that ''n''(''p'') > X<sup>ε</sup> is bounded by a constant depending on ε.<ref name=FI156>{{cite book | title=Opera De Cribro | first1=John B. | last1=Friedlander | author1-link=John Friedlander | first2=Henryk  | last2=Iwaniec | author2-link=Henryk Iwaniec | publisher=[[American Mathematical Society]] | year=2010 | isbn=978-0-8218-4970-5 | zbl=1226.11099  | page=156 }}</ref>

The least quadratic non-residues mod ''p'' for odd primes ''p'' are:
:2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... {{OEIS|id=A053760}}

===Quadratic excess===
Let ''p'' be an odd prime.  The '''quadratic excess''' ''E''(''p'') is the number of quadratic residues on the range (0,''p''/2) minus the number in the range (''p''/2,''p'') {{OEIS|A178153}}.  For ''p'' congruent to 1 mod 4, the excess is zero, since −1 is a quadratic residue and the residues are symmetric under ''r'' ↔ ''p''−''r''.  For ''p'' congruent to 3 mod 4, the excess ''E'' is always positive.<ref>{{cite book | first1=Paul T. | last1=Bateman | author1-link=Paul T. Bateman | first2=Harold G. | last2=Diamond | title=Analytic Number Theory | publisher=World Scientific | year=2004 | isbn=981-256-080-7 | zbl=1074.11001 | page=250 }}</ref>