Editing Quadratic residue (section)

===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>.