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"

m
m
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
Let <math>p</math> be a [[prime number|prime]], and let <math>a</math> be any integer not divisible by <math>p</math>. Then we can define the [[Legendre symbol]] <math>\left(\frac{a}{p}\right)=\begin{cases} 1 & a\mathrm{\ is\ a\ quadratic\ residue\ modulo\ } p, \\ -1 & \mathrm{otherwise}.\end{cases}</math>  
+
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>. We can then define <math>\left(\frac{a}{p}\right)=0</math> if <math>a</math> is divisible by <math>p</math>.
+
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 ==
 
== 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:
 
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} = \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>
  
−
* <math>\left(\frac{-1}{p}\right)=(-1)^{(p-1)/4}</math>.
+
On the other hand, from the lemma,
−
* <math>\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}</math>.
+
<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>
−
* <math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{(p-1)/4\ (q-1)/4}</math>.
+
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>
  
−
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
+
'''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 ==
  
−
* If <math>a\equiv b\pmod{p}</math>, then <math>\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)</math>.
+
* Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,''  American Mathematical Society 2000. ISBN 0-8218-2054-0
−
* <math>\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math>.
 
  
−
There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)
+
[[Category:Number theory]]

Latest revision as of 15:46, 28 April 2016

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 nontrivial multiplicative homomorphism of $\mathbb{F}_p^\times$ into $\mathbb{R}^\times$, extended by $0 \mapsto 0$.

Quadratic Reciprocity Theorem

There are three parts. Let $p$ and $q$ be distinct odd primes. Then the following hold:

  • $\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} .$

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} = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$.

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 .\] 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$

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

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

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

On the other hand, since $K$ is a field of characteristic $p$, \[(\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} .\] Thus \[\zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} .\] Now, if $p \equiv 4 \pm 1 \pmod{8}$, then \[\zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} )\] and $p^2 - 1 \equiv 8 \pmod{16}$, so $(-1)^{(p^2-1)/8} = -1$, and \[\genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} .\] On the other hand, if $p \equiv \pm 1 \pmod{8}$, then \[\zeta^p + \zeta^{-p} = \zeta + \zeta^{-1},\] and $p^2 -1 \equiv 0 \pmod{16}$, so \[\genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} .\] Thus the theorem holds in all cases. $\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=78320"