Difference between revisions of "Quadratic reciprocity"
ComplexZeta (talk | contribs) |
Astroroman (talk | contribs) m |
||
(14 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
− | Let <math>p</math> be a [[prime number|prime]], and let <math>a</math> be any integer | + | 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>. | ||
+ | |||
+ | 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 primes. | + | 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> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | '''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 == | ||
− | * | + | * Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,'' American Mathematical Society 2000. ISBN 0-8218-2054-0 |
− | |||
− | + | [[Category:Number theory]] |
Latest revision as of 15:46, 28 April 2016
Let be a prime, and let be any integer. Then we can define the Legendre symbol
We say that is a quadratic residue modulo if there exists an integer so that .
Equivalently, we can define the function as the unique nontrivial multiplicative homomorphism of into , extended by .
Quadratic Reciprocity Theorem
There are three parts. Let and be distinct odd primes. Then the following hold:
This theorem can help us evaluate Legendre symbols, since the following laws also apply:
- If , then .
- .
There also exist quadratic reciprocity laws in other rings of integers. (I'll put that here later if I remember.)
Proof
Theorem 1. Let be an odd prime. Then .
Proof. It suffices to show that if and only if is a quadratic residue mod .
Suppose that is a quadratic residue mod . Then , for some residue mod , so by Fermat's Little Theorem.
On the other hand, suppose that . Then is even, so is an integer. Since every nonzero residue mod is a root of the polynomial and the nonzero residues cannot all be roots of the polynomial , it follows that for some residue , Therefore is a quadratic residue mod , as desired.
Now, let and be distinct odd primes, and let be the splitting field of the polynomial over the finite field . Let be a primitive th root of unity in . We define the Gaussian sum
Lemma.
Proof. By definition, we have Letting , we have Now, is a root of the polynomial it follows that for , while for , we have Therefore But since there are nonsquares and nonzero square mod , it follows that Therefore by Theorem 1.
Theorem 2. .
Proof. We compute the quantity in two different ways.
We first note that since in , Since , Thus
On the other hand, from the lemma, Since , we then have Since is evidently nonzero and we therefore have as desired.
Theorem 3. .
Proof. Let be the splitting field of the polynomial over ; let be a root of the polynomial in .
We note that So
On the other hand, since is a field of characteristic , Thus Now, if , then and , so , and On the other hand, if , then and , so Thus the theorem holds in all cases.
References
- Helmut Koch, Number Theory: Algebraic Numbers and Functions, American Mathematical Society 2000. ISBN 0-8218-2054-0