Editing Quadratic residue (section)

===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)
|}