Editing Quadratic reciprocity (section)

===Legendre and his symbol===
Fermat proved that if ''p'' is a prime number and ''a'' is an integer, 
:<math>a^p\equiv a \bmod{p}.</math>

Thus if ''p'' does not divide ''a'', using the non-obvious fact (see for example Ireland and Rosen below) that the residues modulo ''p'' form a [[field (mathematics)|field]] and therefore in particular the multiplicative group is cyclic, hence there can be at most two solutions to a quadratic equation:

:<math>a^{\frac{p-1}{2}} \equiv \pm 1 \bmod{p}.</math>

Legendre<ref>This section is based on Lemmermeyer, pp. 6&ndash;8</ref> lets ''a'' and ''A'' represent positive primes ≡ 1 (mod 4) and ''b'' and ''B'' positive primes ≡ 3 (mod 4), and sets out a table of eight theorems that together are equivalent to quadratic reciprocity:

{| class="wikitable"
|+ 
! Theorem
! width="200"|When
! width="200"|it follows that
|-
! I 
| <math>b^{\frac{a-1}{2}}\equiv 1 \bmod{a} </math>
| <math>a^{\frac{b-1}{2}}\equiv 1 \bmod{b} </math>
|-
! II 
| <math>a^{\frac{b-1}{2}}\equiv -1 \bmod{b} </math>
| <math>b^{\frac{a-1}{2}}\equiv -1 \bmod{a} </math>
|-
! III 
| <math>a^{\frac{A-1}{2}}\equiv 1 \bmod{A} </math>
| <math>A^{\frac{a-1}{2}}\equiv 1 \bmod{a} </math>
|-
! IV 
| <math>a^{\frac{A-1}{2}}\equiv -1 \bmod{A} </math>
| <math>A^{\frac{a-1}{2}}\equiv -1 \bmod{a} </math>
|-
! V 
| <math>a^{\frac{b-1}{2}}\equiv 1 \bmod{b} </math>
| <math>b^{\frac{a-1}{2}}\equiv 1 \bmod{a} </math>
|-
! VI 
| <math>b^{\frac{a-1}{2}}\equiv -1 \bmod{a} </math>
| <math>a^{\frac{b-1}{2}}\equiv -1 \bmod{b} </math>
|-
! VII 
| <math>b^{\frac{B-1}{2}}\equiv 1 \bmod{B} </math>
| <math>B^{\frac{b-1}{2}}\equiv -1 \bmod{b} </math>
|-
! VIII 
| <math>b^{\frac{B-1}{2}}\equiv -1 \bmod{B} </math>
| <math>B^{\frac{b-1}{2}}\equiv 1 \bmod{b} </math>
|}

He says that since expressions of the form

:<math>N^{\frac{c-1}{2}}\bmod{c}, \qquad \gcd(N, c) = 1</math>

will come up so often he will abbreviate them as:

:<math>\left(\frac{N}{c}\right) \equiv N^{\frac{c-1}{2}} \bmod{c} = \pm 1.</math>

This is now known as the [[Legendre symbol]], and an equivalent<ref>The equivalence is [[Euler's criterion]]</ref><ref>The analogue of Legendre's original definition is used for higher-power residue symbols</ref> definition is used today: for all integers ''a'' and all odd primes ''p''

:<math>\left(\frac{a}{p}\right) = \begin{cases} 0 & a \equiv 0 \bmod{p} \\ 1 & a \not\equiv 0\bmod{p} \text{ and } \exists x : a\equiv x^2\bmod{p} \\-1 &a \not\equiv 0\bmod{p} \text{ and there is no such } x. \end{cases} </math>

====Legendre's version of quadratic reciprocity====
:<math>\left(\frac{p}{q}\right) = \begin{cases}
 \left(\tfrac{q}{p}\right) & p\equiv 1 \bmod{4} \quad \text{ or } \quad q \equiv 1 \bmod{4} \\
-\left(\tfrac{q}{p}\right) & p \equiv 3 \bmod{4} \quad \text{ and } \quad q \equiv 3 \bmod{4}
\end{cases}</math>

He notes that these can be combined:

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

A number of proofs, especially those based on [[Gauss's lemma (number theory)|Gauss's Lemma]],<ref>E.g. Kronecker's proof (Lemmermeyer, ex. p. 31, 1.34) is to use Gauss's lemma to establish that

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

and then switch ''p'' and ''q''.</ref> explicitly calculate this formula.

====The supplementary laws using Legendre symbols====

:<math>\begin{align}
\left(\frac{-1}{p}\right) &= (-1)^{\frac{p-1}{2}} = \begin{cases} 1 &p \equiv 1 \bmod{4}\\ -1 & p \equiv 3 \bmod{4}\end{cases} \\
\left(\frac{2}{p}\right) &= (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 & p \equiv 1, 7 \bmod{8}\\ -1 & p \equiv 3, 5\bmod{8}\end{cases}
\end{align}</math>

From these two supplements, we can obtain a third reciprocity law for the quadratic character -2 as follows:

For -2 to be a quadratic residue, either -1 or 2 are both quadratic residues, or both non-residues :<math>\bmod p</math>.

So either :<math>\frac{p-1}{2} \text{ or } \frac{p^2-1}{8}</math> are both even, or they are both odd. The sum of these two expressions is

:<math>\frac{p^2+4p-5}{8}</math> which is an integer. Therefore,

:<math>\begin{align}
\left(\frac{-2}{p}\right) &= (-1)^{\frac{p^2+4p-5}{8}} = \begin{cases} 1 & p \equiv 1, 3 \bmod{8}\\ -1 & p \equiv 5, 7\bmod{8}\end{cases}
\end{align}</math>

Legendre's attempt to prove reciprocity is based on a theorem of his:

:'''Legendre's Theorem.''' Let ''a'', ''b'' and ''c'' be integers where any pair of the three are relatively prime. Moreover assume that at least one of ''ab'', ''bc'' or ''ca'' is negative (i.e. they don't all have the same sign). If 
::<math>\begin{align}
u^2 &\equiv -bc \bmod{a} \\
v^2 &\equiv -ca \bmod{b} \\
w^2 &\equiv -ab \bmod{c} 
\end{align}</math>
:are solvable then the following equation has a nontrivial solution in integers:
::<math>ax^2 + by^2 + cz^2=0.</math>

'''Example.''' Theorem I is handled by letting ''a'' ≡ 1 and ''b'' ≡ 3 (mod 4) be primes and assuming that <math>\left (\tfrac{b}{a} \right) = 1</math> and, contrary the theorem, that <math>\left (\tfrac{a}{b} \right ) = -1.</math> Then <math>x^2+ay^2-bz^2=0</math> has a solution, and taking congruences (mod 4) leads to a contradiction.

This technique doesn't work for Theorem VIII. Let ''b'' ≡ ''B'' ≡ 3 (mod 4), and assume

:<math>\left (\frac{B}{b} \right ) = \left (\frac{b}{B} \right ) = -1.</math>

Then if there is another prime ''p'' ≡ 1 (mod 4) such that

:<math>\left (\frac{p}{b} \right ) = \left (\frac{p}{B} \right ) = -1,</math>

the solvability of <math>Bx^2+by^2-pz^2=0</math> leads to a contradiction (mod 4). But Legendre was unable to prove there has to be such a prime ''p''; he was later able to show that all that is required is:

:'''Legendre's Lemma.''' If ''p'' is a prime that is congruent to 1 modulo 4 then there exists an odd prime ''q'' such that <math>\left (\tfrac{p}{q} \right ) = -1.</math>

but he couldn't prove that either. [[#Hilbert symbol|Hilbert symbol (below)]] discusses how techniques based on the existence of solutions to <math>ax^2+by^2+cz^2=0</math> can be made to work.