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
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

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)
m
 
(3 intermediate revisions by 2 users not shown)
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 15: Line 15:
 
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
 
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>.
 
* 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>.
+
* <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.)
 
There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)
Line 30: Line 30:
  
 
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
 
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>
+
<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>,
 
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>
 
<cmath> \bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 . </cmath>
Line 72: Line 72:
  
 
On the other hand, from the lemma,
 
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>
+
<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
 
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>
 
<cmath> \genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q . </cmath>
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  
  
 
[[Category:Number theory]]
 
[[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"