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"

(Event his is better than the one single align... And actually, it's unnatural to call the supplementary laws part if QR)
Line 5: Line 5:
 
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 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>.
+
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 ==
Line 110: Line 110:
 
== References ==
 
== References ==
  
−
* Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,''  American Mathematical Society 2000.  ISBN 0-8218-2054-0 begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting.
+
* Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,''  American Mathematical Society 2000.  ISBN 0-8218-2054-0 begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting.
  
 
[[Category:Number theory]]
 
[[Category:Number theory]]

Revision as of 07:00, 15 August 2010

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

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 begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting.
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Quadratic_reciprocity&oldid=35647"