AoPSWiki

Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!

Personal tools

Search

Toolbox

Quadratic reciprocity

From AoPSWiki

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

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} , \\\genfr...$ This theorem can help us evaluate Legendre symbols, since the following laws also apply:

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{...$ 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...$ 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}\...$ 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 ...$ 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} \z...$ 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)...$ 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 "http://www.artofproblemsolving.com/Wiki/index.php/Quadratic_reciprocity"

Category: Number theory

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us