View source for Quadratic reciprocity

Let <math>p</math> be a [[prime number|prime]], and let <math>a</math> be any integer. Then we can define the [[Legendre symbol]]
<cmath> \genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p, \\
0 & \text{if } p \text{ divides } a, \\ -1 & \text{otherwise}.\end{cases} </cmath>

We say that <math>a</math> is a '''quadratic residue''' modulo <math>p</math> if there exists an integer <math>n</math> so that <math>n^2\equiv a\pmod p</math>.

Equivalently, we can define the function <math>a \mapsto \genfrac{(}{)}{}{}{a}{p}</math> as the unique nontrivial multiplicative [[homomorphism]] of <math>\mathbb{F}_p^\times</math> into <math>\mathbb{R}^\times</math>, extended by <math>0 \mapsto 0</math>.

== Quadratic Reciprocity Theorem ==

There are three parts. Let <math>p</math> and <math>q</math> be distinct [[odd integer | odd]] primes. Then the following hold:
* <math>\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2},</math>
* <math> \genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2-1)/8},</math>
* <math>\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4} .</math>
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
* If <math>a\equiv b\pmod{p}</math>, then <math>\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}</math>.
* <math>\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}</math>.

There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)

== Proof ==

'''Theorem 1.''' Let <math>p</math> be an odd prime.   Then <math>\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}</math>.

''Proof.'' It suffices to show that <math>(-1)^{(p-1)/2} = 1</math> if and only if <math>-1</math> is a quadratic residue mod <math>p</math>.

Suppose that <math>-1</math> is a quadratic residue mod <math>p</math>.  Then <math>k^2 = -1</math>, for some residue <math>k</math> mod <math>p</math>, so
<cmath> (-1)^{(p-1)/2} = (k^2)^{(p-1)/2} = k^{p-1} = 1 = \genfrac{(}{)}{}{}{-1}{p} , </cmath>
by [[Fermat's Little Theorem]].

On the other hand, suppose that <math>(-1)^{(p-1)/2} = 1</math>.  Then <math>(p-1)/2</math> is even, so <math>(p-1)/4</math> is an integer.  Since every nonzero residue mod <math>p</math> is a root of the polynomial
<cmath> (x^{p-1} - 1) = (x^{(p-1)/2} + 1)(x^{(p-1)/2} - 1) , </cmath>
and the <math>p-1</math> nonzero residues cannot all be roots of the polynomial <math>x^{(p-1)/2} - 1</math>, it follows that for some residue <math>k</math>,
<cmath> \bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 . </cmath>
Therefore <math>-1</math> is a quadratic residue mod <math>p</math>, as desired.  <math>\blacksquare</math>

Now, let <math>p</math> and <math>q</math> be distinct odd primes, and let <math>K</math> be the [[splitting field]] of the polynomial <math>x^q - 1</math> over the finite field <math>\mathbb{F}_p</math>.  Let <math>\zeta</math> be a primitive <math>q</math>th root of unity in <math>K</math>.  We define the Gaussian sum
<cmath> \tau_q = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^q . </cmath>

'''Lemma.''' <math>\tau_q^2 = q (-1)^{(q-1)/2}</math>

''Proof.''  By definition, we have
<cmath> \tau_q^2 = \sum_a \sum_b \genfrac{(}{)}{}{}{a}{q} \zeta^a \genfrac{(}{)}{}{}{b}{q} \zeta^b = \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} . </cmath>
Letting <math>c \equiv a^{-1}b \pmod{q}</math>, we have
<cmath> \begin{align*} \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} &= \sum_{a\neq 0} \sum_c \genfrac{(}{)}{}{}{a^2 c}{q} \zeta^{a+ac} \\
&= \sum_c \sum_{a \neq 0} \genfrac{(}{)}{}{}{c}{q} \bigl( \zeta^{1+c} \bigr)^a \\
&= \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a . \end{align*} </cmath>
Now, <math>\zeta^{c+1}</math> is a root of the polynomial
<cmath> P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i, </cmath>
it follows that for <math>c\neq -1</math>,
<cmath> \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1, </cmath>
while for <math>c = -1</math>, we have
<cmath> \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 . </cmath>
Therefore
<cmath> \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q \genfrac{(}{)}{}{}{-1}{q} - \sum_{c=0}^{q-1}\genfrac{(}{)}{}{}{c}{q} . </cmath>
But since there are <math>(q-1)/2</math> nonsquares and <math>(q-1)/2</math> nonzero square mod <math>q</math>, it follows that
<cmath> \sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 . </cmath>
Therefore
<cmath> \tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} , </cmath>
by Theorem 1.

'''Theorem 2.''' <math>\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}</math>.

''Proof.''  We compute the quantity <math>\tau_q^p</math> in two different ways.

We first note that since <math>p=0</math> in <math>K</math>,
<cmath> \tau_q^p = \biggl( \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^a \biggr)^p = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q}^p \zeta^{ap} = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} . </cmath>
Since <math>\genfrac{(}{)}{}{}{p}{q}^2 = 1</math>,
<cmath> \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{p}{q} \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{pa}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{a}{q} \tau_q . </cmath>
Thus
<cmath> \tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q . </cmath>

On the other hand, from the lemma,
<cmath> \tau_q^p = (\tau_q^2)^{(p-1)/2} \cdot \tau_q = \bigl[ q (-1)^{(q-1)/2} \bigr]^{(p-1)/2} \tau_q = q^{(p-1)/2} (-1)^{(p-1)(q-1)/4 \tau_q . </cmath>
Since <math>q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}</math>, we then have
<cmath> \genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q . </cmath>
Since <math>\tau_q</math> is evidently nonzero and
<cmath> \genfrac{(}{)}{}{}{q}{p}^2 = 1, </cmath>
we therefore have
<cmath> \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}, </cmath>
as desired.  <math>\blacksquare</math>

'''Theorem 3.''' <math>\genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2 - 1)/8}</math>.

''Proof.''  Let <math>K</math> be the splitting field of the polynomial
<math>x^8-1</math> over <math>\mathbb{F}_p</math>; let <math>\zeta</math> be a root of the polynomial
<math>x^4+1</math> in <math>K</math>.

We note that
<cmath> (\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2 + \zeta^{-2} (\zeta^{4} + 1) = 2 . </cmath>
So
<cmath> (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1}) 2^{(p-1)/2} = (\zeta + \zeta^{-1}) \genfrac{(}{)}{}{}{2}{p}. </cmath>

On the other hand, since <math>K</math> is a field of characteristic <math>p</math>,
<cmath> (\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} . </cmath>
Thus
<cmath> \zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} . </cmath>
Now, if <math>p \equiv 4 \pm 1 \pmod{8}</math>, then
<cmath> \zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} ) </cmath>
and <math>p^2 - 1 \equiv 8 \pmod{16}</math>, so <math>(-1)^{(p^2-1)/8} = -1</math>,
and
<cmath> \genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} . </cmath>
On the other hand, if <math>p \equiv \pm 1 \pmod{8}</math>, then
<cmath> \zeta^p + \zeta^{-p} = \zeta + \zeta^{-1}, </cmath>
and <math>p^2 -1 \equiv 0 \pmod{16}</math>, so
<cmath> \genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} . </cmath>
Thus the theorem holds in all cases. <math>\blacksquare</math>


== References ==

* Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,''  American Mathematical Society 2000.  ISBN 0-8218-2054-0 

[[Category:Number theory]]