Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Quadratic reciprocity"

(cleaned the LaTeX a bit; I'll add a proof later)
(added proof of the main result)
Line 20: Line 20:
  
 
There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)
 
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>
 +
 +
== References ==
 +
 +
* Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,''  American Mathematical Society 2000.  ISBN 0-8218-2054-0.
 +
 +
[[Category:Number theory]]

Revision as of 23:26, 23 March 2009

Let $p$ be a prime, and let $a$ be any integer. Then we can define the Legendre symbol \[\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}\]

We say that $a$ is a quadratic residue modulo $p$ if there exists an integer $n$ so that $n^2\equiv a\pmod p$.

Equivalently, we can define the function $a \mapsto \genfrac{(}{)}{}{}{a}{p}$ as the unique nonzero multiplicative homomorphism of $\mathbb{F}_p$ into $\mathbb{R}$.

Quadratic Reciprocity Theorem

There are three parts. Let $p$ and $q$ be distinct odd primes. Then the following hold: \begin{align*} \genfrac{(}{)}{}{}{-1}{p} &= (-1)^{(p-1)/2} , \\ \genfrac{(}{)}{}{}{2}{p} &= (-1)^{(p^2-1)/8} , \\ \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} &= (-1)^{(p-1)(q-1)/4} . \end{align*} This theorem can help us evaluate Legendre symbols, since the following laws also apply:

  • If $a\equiv b\pmod{p}$, then $\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}$.
  • $\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$ (Error compiling LaTeX. Unknown error_msg).

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

Proof

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

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

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

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

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

Lemma. $\tau_q^2 = q (-1)^{(q-1)/2}$

Proof. By definition, we have \[\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} .\] Letting $c \equiv a^{-1}b \pmod{q}$, we have \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*} Now, $\zeta^{c+1}$ is a root of the polynomial \[P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i,\] it follows that for $c\neq -1$, \[\sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1,\] while for $c = -1$, we have \[\sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 .\] Therefore \[\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} .\] But since there are $(q-1)/2$ nonsquares and $(q-1)/2$ nonzero square mod $q$, it follows that \[\sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 .\] Therefore \[\tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} ,\] by Theorem 1.

Theorem 2. $\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}$.

Proof. We compute the quantity $\tau_q^p$ in two different ways.

We first note that since $p=0$ in $K$, \[\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} .\] Since $\genfrac{(}{)}{}{}{p}{q}^2 = 1$, \[\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 .\] Thus \[\tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q .\]

On the other hand, from the lemma, 

\[\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 .\] (Error compiling LaTeX. Unknown error_msg)

Since $q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}$, we then have \[\genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q .\] Since $\tau_q$ is evidently nonzero and \[\genfrac{(}{)}{}{}{q}{p}^2 = 1,\] we therefore have \[\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4},\] as desired. $\blacksquare$

References

  • Helmut Koch, Number Theory: Algebraic Numbers and Functions, American Mathematical Society 2000. ISBN 0-8218-2054-0.
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Quadratic_reciprocity&oldid=30953"