What's the "best" proof of quadratic reciprocity? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T12:03:30Z http://mathoverflow.net/feeds/question/1420 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity What's the "best" proof of quadratic reciprocity? Ben Webster 2009-10-20T13:00:34Z 2013-04-20T22:10:46Z <p>For my purposes, you may want to interpret "best" as "clearest and easiest to understand for undergrads in a first number theory course," but don't feel too constrained.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1422#1422 Answer by Peter McNamara for What's the "best" proof of quadratic reciprocity? Peter McNamara 2009-10-20T13:15:59Z 2009-11-26T16:04:03Z <p>The easiest to understand line by line are the elementary proofs that go through Gauss' Lemma, and are likely to be seen in any elementary number theory book. I've never actually liked these proofs personally and prefer the one at the start of Serre's "A Course in Arithmetic" for a proof without many technical prerequisites (finite fields only from memory).</p> <p>Edit: Less elementarily, one could argue that any 'best' proof will necessarily be adelic, proving that the product of the Hilbert symbols over all places at rational arguments is 1. For a geometric example of such an argument, I'm going to throw out <a href="http://arxiv.org/abs/0804.2142" rel="nofollow">arXiv:0804.2142</a> and references therein, primarily because I don't know if there exists an analogous argument using a central extension of GL_1 in the number field case.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1431#1431 Answer by Qiaochu Yuan for What's the "best" proof of quadratic reciprocity? Qiaochu Yuan 2009-10-20T14:04:41Z 2009-10-20T14:04:41Z <p>I'm a fan of <a href="http://slugmath.ucsc.edu/mediawiki/index.php/State/Quadratic_reciprocity#tab=Zolotarev.27s_Proof" rel="nofollow">Zolotarev's proof</a>, although the proof by Gauss's lemma does have sentimental value.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1452#1452 Answer by Jared Weinstein for What's the "best" proof of quadratic reciprocity? Jared Weinstein 2009-10-20T16:46:52Z 2009-10-20T16:46:52Z <p>The proof involving Gauss sums always seemed the best to me. I'm going to run my own undergrad number theory students through that proof, right after we develop some experience with roots of unity. </p> <p>If you remove the constraint of accessibility to students of a first number theory course, then you can avoid computations with roots of unity altogether: By Galois theory (and some knowledge of discriminants), a square root of p or -p lives inside of the cyclotomic field of index p. An examination of the action of a Frobenius element at q on this square root relates Legendre(p,q) to Legendre(q,p). </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1455#1455 Answer by Alon Amit for What's the "best" proof of quadratic reciprocity? Alon Amit 2009-10-20T17:14:28Z 2013-04-15T07:15:15Z <p>I don't think anyone mentioned Eisenstein's classic proof. <a href="http://www.math.nmsu.edu/~history/eisenstein/eisenstein.html" rel="nofollow">This presentation</a> of it is pretty good. I find it clear and attractive, especially because it sort of avoids Gauss' Lemma (which is a clever gadget but somehow off-putting). </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1457#1457 Answer by watchmath for What's the "best" proof of quadratic reciprocity? watchmath 2009-10-20T17:32:02Z 2009-10-20T17:32:02Z <p>The pdf version of the Eisenstein's proof mentioned by Alon above can be download from jstor: <a href="http://www.jstor.org/stable/2687081?&amp;Search=yes&amp;term=Theorem&amp;term=Misunderstood&amp;term=Eisenstein%27s&amp;term=Quadratic&amp;term=Geometric&amp;term=Reciprocity&amp;term=Proof&amp;list=hide&amp;searchUri=%2Faction%2FdoBasicSearch%3FQuery%3DEisenstein%2527s%2BMisunderstood%2BGeometric%2BProof%2Bof%2Bthe%2BQuadratic%2BReciprocity%2BTheorem%2B%26gw%3Djtx%26prq%3DEisenstein%2527s%2BMisunderstood%2BGeometric%2BProof%2Bof%2Bthe%2BQuadratic%2BReciprocity%2BTheorem%2BReinhard%2BC.%2BLaubenbacher%2B-%2BDavid%2BJ.%2BPengelley%26Search%3DSearch%26hp%3D25%26wc%3Don&amp;item=1&amp;ttl=1&amp;returnArticleService=showArticle" rel="nofollow">link text</a></p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1458#1458 Answer by MRB for What's the "best" proof of quadratic reciprocity? MRB 2009-10-20T17:37:45Z 2009-10-20T17:37:45Z <p>The proof involving Gauss sums seems to be the most standard one.</p> <p>There is also Tim Kuniskys <a href="http://www.thehcmr.org/issue2%5F2/math%5Fminutiae.pdf" rel="nofollow">proof</a> using only basic group theory, which for me makes the theorem a bit less misterious. </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1468#1468 Answer by Joel Dodge for What's the "best" proof of quadratic reciprocity? Joel Dodge 2009-10-20T18:46:34Z 2009-10-20T18:46:34Z <p>I think my favorite proof that's accessible to undergrads is Eisenstein's proof using the sine function. If we raise the bar on the prerequisites though, my favorite proof (the one that I would give if someone demanded a proof!) is the one using basic algebraic number theory and Galois theory. That's largely because this is a family of ideas that is useful for much more than "just" proving quadratic reciprocity. </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1472#1472 Answer by Noah Snyder for What's the "best" proof of quadratic reciprocity? Noah Snyder 2009-10-20T19:31:56Z 2013-04-20T22:01:01Z <p>I think by far the simplest easiest to remember elementary proof of QR is due to <a href="http://tinyurl.com/3z62fdw" rel="nofollow">Rousseau</a>. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).</p> <p>Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.</p> <p>In more detail. First let me describe the three "obvious" halves:</p> <ol> <li>Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor</li> <li>Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$</li> <li>Take the first half of $(\mathbb{Z}/pq)^\times$</li> </ol> <p>The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):</p> <ol> <li>$(P!^{q-1}, (q-1)!^P)$</li> <li>$((p-1)!^Q, Q!^{q-1})$</li> <li>$(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!})$</li> </ol> <p>All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1490#1490 Answer by rita the dog for What's the "best" proof of quadratic reciprocity? rita the dog 2009-10-20T21:01:08Z 2010-07-09T21:25:39Z <p>Kevin Brown has a nice expository article <a href="http://www.mathpages.com/home/kmath075.htm" rel="nofollow">Jewel of Arithmetic</a> </p> <p>and Franz Lemmermeyer has compiled a <a href="http://www.rzuser.uni-heidelberg.de/~hb3/rchrono.html" rel="nofollow">list of all published proofs</a></p> <p>both of which are worth a look.</p> <hr> <p>Edit: I just thought I'd add that there are 224 published proofs in Franz Lemmermeyer's list, and if you are using frames and if your institution subscribes to the online version of Mathematical reviews or Zentralblatt, then the reviews will appear in one of the frames. </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1506#1506 Answer by Thomas Riepe for What's the "best" proof of quadratic reciprocity? Thomas Riepe 2009-10-20T22:20:44Z 2009-10-20T22:20:44Z <p>I found <a href="http://www.neverendingbooks.org/DATA/KapranovSmirnov.pdf" rel="nofollow" title="Cohomology determinants and reciprocity laws">this</a> connection with linking numbers very fascinating and <a href="http://math.stanford.edu/~lekheng/flt/ash-gross.pdf" rel="nofollow" title="Generalized Non-Abelian Reciprocity Laws">this</a> discussion of generalizations.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/1793#1793 Answer by David Corwin for What's the "best" proof of quadratic reciprocity? David Corwin 2009-10-22T03:10:06Z 2009-10-22T03:10:06Z <p>I'm told that the Gauss sum argument gets generalized to class field theory, but do any of the other arguments generalize? Do you ever see them again in higher math?</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/6882#6882 Answer by Guillermo Mantilla for What's the "best" proof of quadratic reciprocity? Guillermo Mantilla 2009-11-26T09:23:40Z 2009-11-26T09:23:40Z <p>A great proof, inspired by Zolotarev's paper mentioned above, can be found in a very nice paper by Duke and Hopkins. <a href="http://www.math.ucla.edu/~wdduke/preprints/duke-main.pdf" rel="nofollow">http://www.math.ucla.edu/~wdduke/preprints/duke-main.pdf</a>. </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/6892#6892 Answer by Simon for What's the "best" proof of quadratic reciprocity? Simon 2009-11-26T15:29:43Z 2009-11-26T15:29:43Z <p>There's a nice proof that involves the computation of <code>$K_2(\mathbb{Q})$</code> and the interpretation of <code>$K_2$</code> as a universal symbol (i.e. a bilinear map $\mathbb{Q}^\times\times\mathbb{Q}^\times\to A$ for some abelian group $A$, written multiplicatively, satisfying $(a,1-a)=1$) in Milnor's book on algebraic $K$ theory. The tame symbols are interpreted as Legendre symbols, and by universality of <code>$K_2$</code> as a symbol Tate claims that this proof is essentially Gauss's original argument. I suspect that this argument can be generalized to other totally real number fields, but explicit computations of <code>$K_2(F)$</code> aren't very easy for large discriminants.</p> <p>It's definitely not the easiest to understand, but at the moment, it's my favorite.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/12345#12345 Answer by KConrad for What's the "best" proof of quadratic reciprocity? KConrad 2010-01-19T22:50:44Z 2010-01-20T00:57:35Z <p>The question asked for the nicest proof for a first undergraduate course. Has anyone who offered a proposal used their favorite choice in a course? (Obviously the suggestions referring to K-theory or Hilbert symbols weren't suggested in that spirit.) I've taught an undergrad number theory class several times and initially I gave the Gauss sum proof. But I realized afterwards that to the students this truly comes out of nowhere (it seems too magical), so I hunted around for other proofs, preferably some which build on more basic ideas that I could present earlier in the course. The Eisenstein (sine-function) proof doesn't fit that requirement, and Zolotarev seems too far-out if the students have not had group theory (which most have not). So what else is available?</p> <p>There is a proof due to V. Lebesgue (not H. Lebesgue!) that is based on counting points on hyperspheres mod p. It can be found in Ireland-Rosen's book. For an odd prime p and positive integer n, let </p> <p>N_n(p) = #{(x_1,....,x_n) \in (Z/p)^n : x_1^2 + ... + x_n^2 = 1}.</p> <p>This is the number of mod p points on the sphere in n-space mod p. Earlier in the course I have the students discover numerically that every number mod p is a sum of two squares. That is, </p> <p>#{(x,y) \in (Z/p)^2 : x^2 + y^2 = a}</p> <p>is positive for every a in Z/p. This could be shown by the pigeonhole principle, since x^2 and a - y^2 each take (p+1)/2 values mod p and thus have an overlap. But more precisely, if you look at examples, you quickly discover that this 2-variable count is independent of a when a is nonzero (from a more adv. point of view, the independence is because the norm map on unit groups ((Z/p)[t]/(t^2+1))* --> (Z/p)* is a homomorphism so its fibers have the same size, but <em>that</em> is a crazy explanation in an elem. number theory course). Enough data suggests what that uniform value is for any nonzero a mod p, and then we prove that in class. With this 2-variable count we return to the hypersphere count and get a simple recursive formula connecting N_n(p) to N_{n-2}(p). If you let n = q be an odd prime, the recursive formula involves p^((q-1)/2) plus N_{q-2}(p) times a multiple of q, so N_q(p) mod q involves (p|q). [Note: Although the application will use N_q(p), you <em>must</em> think about N_n(p) for general n first since the recursion from n back to n-2 makes no sense in general when the number of variables is only an odd prime: n-2 usu. isn't prime when n is.] </p> <p>At the same time, the set being counted by N_n(p) is invariant under cyclic shifts of the coordinates. On the very first problem set I have the students discover numerically that the number of cyclic shifts of an n-tuple is always a divisor of n. So when we let n = q be an odd prime, N_n(p) = N_q(p) is the number of constant q-tuples on the unit sphere mod p plus a multiple of q. A constant q-tuple is basically counting whether or not q mod p is a square. So N_q(p) mod q is related to (q|p). </p> <p>In the two approaches to counting N_q(p) mod q, one involves (p|q) and the other involves (q|p). This implies the QR relation mod q, which is actual equality since 1 is not -1 mod q.</p> <p>One nice thing about this approach is that it can also be used to prove the supplementary law for (2|p), by counting </p> <p>#{(x,y) \in (Z/p)^2 : x^2 + y^2 = 1} mod p</p> <p>in two ways. First there is the exact formula for the count (not just mod p) which I mentioned before. Second, most solutions in this count come in packets of size 8 (permute coordinates and change signs to get 8 solutions out of one solution). The exceptions which don't fall into packets of size 8 (when x is +/-y mod p or x or y is 0 mod p) depend on whether or not 2 mod p is a square (does 2x^2 = 1 mod p have a solution?), and comparing these two formulas mod p implies the usual rule for (2|p). </p> <p>Since I am able to get the students to work on ideas that are used in the proof much earlier on during the semester (one doesn't need quadratic residues to numerically look at solutions of x^2 + y^2 = a mod p, for instance), this proof nicely ties together things they have seen throughout the course. So that's why this is my vote for the best proof to give in an undergrad course.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/13719#13719 Answer by Mark B Villarino for What's the "best" proof of quadratic reciprocity? Mark B Villarino 2010-02-01T18:25:57Z 2010-02-01T18:25:57Z <p>Gauss' original inductive proof is the most natural proof to me. It is a computationally based induction on the maximum of the two primes p and q, and is far and away the most natural. Here, natural does not mean easy or elegant. It means a proof that arises naturally from the numerical patterns. Gauss computes the special cases of quadratic reprocity in a table in the back of his "Disquisitiones" from which it is fairly easy to guess which numbers are residues or non residues of given prime. He carries out the examples of p=2,3,5, 7 and the patterns start to show clearly. He gives an induction proof for some of those cases, indicating the structure of the general induction proof. </p> <p>Admittedly, Gauss, himself, looked for other proofs. Nevertheless, the first proof shows WHY the theorem is true in a way which the subsequent clever proofs do not. </p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/13746#13746 Answer by Mark B Villarino for What's the "best" proof of quadratic reciprocity? Mark B Villarino 2010-02-01T22:01:13Z 2010-02-01T22:01:13Z <p>Gauss' original proof is to be in Gauss' Disquisitiones (English translation published by Springer): the residues -1 and +1 on pages 72-73, the residues +2 and -2 on pages 73-77, +3 and -3 on pages77-78, residues +5 and -5 on pages 79-82, +7 and -7 on page 82...the general law of reciprocity is stated on page-87-88, and the proof is carried out on pp 88-98.</p> <p>There is a very fine presentation of the Gauss' general inductive proof in the textbook <em>Introduction to Number Theory</em> by Daniel E. Flath, on pages 77-80. I have given this proof (Gauss' treatment of the residues +2, -2, +3, -3, and Flath's version of the general proof) repeatedly in my classes in the University of Costa Rica and the students have responded quite positively.</p> <p>Finally it can also be found in Mathews, <em>Number Theory</em>, but uses properties of the Jacobi symbol. Gauss used and stated these properties, but did not introduce a separate definition, and of course never used the Legendre symbol.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/66201#66201 Answer by Chandrasekhar for What's the "best" proof of quadratic reciprocity? Chandrasekhar 2011-05-27T16:35:45Z 2011-05-27T16:35:45Z <p>I don't really know who discovered this proof, but it's interesting. It is taken from Prof. Ram Murty's website:</p> <ul> <li><a href="http://www.mast.queensu.ca/~murty/quad1.dvi" rel="nofollow">http://www.mast.queensu.ca/~murty/quad1.dvi</a></li> </ul> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/71242#71242 Answer by Franz Lemmermeyer for What's the "best" proof of quadratic reciprocity? Franz Lemmermeyer 2011-07-25T16:00:02Z 2011-07-25T16:00:02Z <p>The following variant of a proof going back to V. Lebesgue and Eisenstein is due to Aurelien Bessard (2010). See also W. Castryck, <em> A shortened classical proof of the quadratic reciprocity law</em>, Amer. Math. Monthly <b>115</b> (2008), 550-551.</p> <p>Let $p = 2m+1$ and $q$ be distinct odd primes and let $N$ denote the number of solutions of the equation $$x_1^2 + \ldots + x_p^2 = 1$$ in the finite field ${\mathbb F}_q$. </p> <ol> <li><p>The group ${\mathbb Z}/p{\mathbb Z}$ acts on the solution space $X$ by shifting indices: if $(x_1, \ldots, x_p) \in X$, then so is $(x_a,x_{a+1}, \ldots)$ for each $a \in {\mathbb Z}/p{\mathbb Z}$, where the indices have to be read modulo $p$. Each orbit has exactly $p$ elements except if there is an $x$ with $(x,x,\ldots,x) \in X$: the orbit of this element has $1$ element. Now $(x,x,\ldots,x) \in X$ if and only if $px^2 = 1$ is solvable in ${\mathbb F}_q$, hence $$N \equiv \Big( \frac pq \Big) + 1 \bmod p.$$</p></li> <li><p>We make a change of variables to transform the diagonal equation into an equation where counting the number of solutions is easier. To this end, consider the matrix $$A = \left( \begin{matrix} 0 &amp; 1 &amp; &amp; &amp; &amp; &amp; &amp; \\ 1 &amp; 0 &amp; &amp; &amp; &amp; &amp; &amp; \\ &amp; &amp; 0 &amp; 1 &amp; &amp; &amp; &amp; \\ &amp; &amp; 1 &amp; 0 &amp; &amp; &amp; &amp; \\ &amp; &amp; &amp; &amp; \ddots &amp; &amp; &amp; \\ &amp; &amp; &amp; &amp; &amp; 0 &amp; 1 &amp; \\<br> &amp; &amp; &amp; &amp; &amp; 1 &amp; 0 &amp; \\<br> &amp; &amp; &amp; &amp; &amp; &amp; &amp; a<br> \end{matrix} \right)$$ with $a = (-1)^{(p-1)/2}$. Since $\det A = 1$, this matrix is congruent to the unit matrix, hence $X$ and the solution spaces $X'$ of the equation $x^T A x = 1$, i.e., of $$2(y_1z_1 + \ldots + y_m z_m) + ax_p^2 = 1$$ are isomorphic (recall that $p = 2m+1$). </p> <p>For counting the number of solutions of $X'$, observe that if $(y_1, \ldots, y_m) = 0$, we have $q^m \cdot (1+a^{(q-1)/2})$ possibilities for choosing $z_1, \ldots, z_m$ and $x_p$. </p> <p>If $y = (y_1, \ldots, y_m) \ne 0$, on the other hand, then for each choice of $y$ and $x_p$ we have to count the number of points on a hyperplane of dimension $m$; there are $q^{m-1}$ points on such a hyperplane, and the number of overall possibilities in this case is $(q^m-1) \cdot q \cdot q^{m-1} = q^m(q^m-1)$. </p></li> <li><p>Thus we find \begin{align*} N &amp; = q^m (1+a^{(q-1)/2} + q^m(q^m-1) = q^m(q^m + (-1)^{\frac{p-1}2 \frac{q-1}2}) \\ &amp; \equiv \Big(\frac qp \Big) \Big[ \Big(\frac qp \Big) + (-1)^{\frac{p-1}2 \frac{q-1}2} \Big] \equiv 1 + (-1)^{\frac{p-1}2 \frac{q-1}2} \Big(\frac qp \Big) \bmod p. \end{align*} Comparing with the congruence from 1. gives the quadratic reciprocity law.</p></li> </ol> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/71282#71282 Answer by Moosbrugger for What's the "best" proof of quadratic reciprocity? Moosbrugger 2011-07-26T01:51:29Z 2011-07-26T01:51:29Z <p>There was some discussion above about how the proof with Gauss sums is hard to motivate. I disagree, but the motivation involves a little more (mild) algebraic number theory (i.e., Galois theory, algebraic integers, characteristic zero...) than appears in the shortened proof in Serre's book on arithmetic.</p> <p>(This is of course well-known to number theorists, but I'll write up the full argument just in case somebody has only ever seen the more magical presentation with Gauss sums before.)</p> <p>Let $p,q$ be odd, distinct primes below.</p> <p>1) $\mathbb{Q}(\zeta_p)$ has Galois group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and therefore contains a unique subfield of degree $2$ over $\mathbb{Q}$. It's straight-forward to compute (without knowing what a Gauss sum is) a non-trivial element of this extension with rational square: it's the Gauss sum $G=\sum (\frac{a}{p})\cdot(\zeta_p)^a$.</p> <p>2) By construction, $G^2\in\mathbb{Q}$. What is it? It's easy to see from the formula above that $|G|^2=p$. Moreover, also by the formula, the complex conjugate $\overline{G}$ equals $G$ iff $p=1\mod 4$ and $\overline{G}=-G$ iff $G=3\mod 4$. Therefore, $G=\pm \sqrt{p}$ or $G=\pm\sqrt{-p}$ depending on the residue class of $p$ modulo $4$.</p> <p>This is the major upshot: we have a very convenient expression for (a variant of) $\sqrt{p}$ now.</p> <p>3) Note that $G$ is an algebraic integer. Therefore, we can reduce it modulo $q$. Since $\mathbb{Q}(G)$ is a quadratic extension of $\mathbb{Q}$ (namely: $\mathbb{Q}[\sqrt{\pm p}]$), the induced extension of $\mathbb{F}_q$ is an extension of degree $\leq 2$.</p> <p>4) Is this extension $\mathbb{F}_q$ or the unique quadratic extension of $\mathbb{F}_q$? Well, it suffices to check whether or not $G\in\mathbb{F}_q$. To do this, you can use the Frobenius at $q$. It's easy to see in this way that $G^q=(\frac{q}{p})\cdot G$ (by the formula for $G$). So the extension has degree one if $(\frac{q}{p})=1$ and degree two if $(\frac{q}{p})=-1$.</p> <p>5) But since we know that $G=\sqrt{\pm p}$ (again: depending on the residue class of $p$ mod $4$), we see that we can give a second answer to the question in 4): $G$ defines an extension of degree $1$ if: a) $p=1\mod 4$ and $p$ is a quadratic residue mod $q$ or b) $p=3\mod 4$, $\sqrt{-1}\not\in\mathbb{F}_q$ (which is the same as $q=3 \mod 4$) and $\sqrt{p}\not\in\mathbb{F}_q$.</p> <p>6) Comparing the answers to the above questions, we see that $q$ is a quadratic residue mod $p$ if and only if the conditions from 5) are satisfied. But these are exactly the conditions from quadratic reciprocity.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/94080#94080 Answer by Ken for What's the "best" proof of quadratic reciprocity? Ken 2012-04-15T00:53:34Z 2012-04-15T00:53:34Z <p>I recommend Gauss's third proof with modifications by Eisenstein. In my opinion, it is by far the clearest and most straight-forward proof of Quadratic Reciprocity even though it is not the shortest. The proof makes no use of any mathematical discipline other than elementary number theory. That is, it uses no abstract algebra or combinatorics. Its charm is that it uses the greatest integer function in an advanced way in place of any advanced theory. The proof uses the greatest integer function to express a variety of number-theoretic concepts and statements involving integers mathematically. Then, using properties of the greatest integer function, the proof works with these concepts and statements concretely (by manipulating them mathematically) to achieve the result. Gauss invented the greatest integer function for his third proof of QR in 1808 for this very purpose. Since it was long and messy, it was simplified by Eisenstein in 1844. </p> <p>How a proof is presented by the author is also important. In my online text, "A Mathematical Analysis of the Greatest Integer Function", I include a full treatment of QR. For Gauss's third proof, I used Dence. His book, "Elements of the Theory of Numbers" is an advanced text and I felt that his presentation of the proof contained gaps. While his presentation might be appropriate for his objectives and target audience, I felt that it would seem more like an outline to undergraduate students. For this reason, when rewriting the proof, I took three measures to provide clarity. I put a lot of effort into closing every gap and providing a thorough explanation for certain parts, which accounts for a lot of its length. Since the proof has many components even after modifications by Eisenstein, I organized it by dividing it into sub-objectives and providing sub-proofs for each. I also include all three lattice-point diagrams with a numerical example in full detail. So, if you want to savor Gauss's third proof with modifications by Eisenstein, then you want to read my online text at www.greatestintegerfunctionresearch.org. My online text is also an excellent resource for various topics in number theory and analysis and is chockfull of original research.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/99362#99362 Answer by BenjaLim for What's the "best" proof of quadratic reciprocity? BenjaLim 2012-06-12T12:56:26Z 2012-06-27T00:19:16Z <p>Several people above have mentioned the proof above using Gauss sums. In a recent assignment for our Galois theory course, we were asked to prove quadratic reciprocity using Galois theory. I would like to remark that in determining the fixed field of degree 2 over $\Bbb{Q}$ corresponding to the subgroup of index $2$ in $\textrm{Gal}(\Bbb{Q}(\zeta_p)/\Bbb{Q})$, one does not need to know about Gauss sums. Instead notice that $\Bbb{Q}(\zeta_p)$ is the splitting field of $x^p -1$, so that the discriminant of this polynomial $(-1)^{p(p-1)/2}p^p$ is in $\Bbb{Q}(\zeta_p)$. The discriminant can be computed easily using the Vandermonde determinant and some knowledge about power sums. </p> <p>Since the square root of the discriminant is a product of differences of roots, it too is in the splitting field. Hence we see that $\Bbb{Q}(\sqrt{\pm p })$ is the unique subfield of index 2 contained in $\Bbb{Q}(\zeta_p)$, depending on whether $p \equiv 1$ or $3$ mod $4$.</p> <p>Keith Conrad remarked above that in the usual proof using Gauss sums, we need to show that $1 \equiv -1 \mod(p\Bbb{Z}[\zeta_p])$ gives us our desired contradiction, or that $2/p \in \Bbb{Z}[\zeta_p]$ gives a contradiction. I believe one can do this without invoking anything about integral bases. Instead we can say by Proposition 5.1(iii) of Atiyah - Macdonald that $2/p$ is integral over $\Bbb{Z}$ and since $\Bbb{Z}$ is integrally closed in its field of fractions (the proof of which can be rephrased entirely without any commutative algebra) this forces $2/p$ to be an integer. But by assumption $p$ was a prime not equal to 2 so this is a contradiction.</p> http://mathoverflow.net/questions/1420/whats-the-best-proof-of-quadratic-reciprocity/128198#128198 Answer by ACL for What's the "best" proof of quadratic reciprocity? ACL 2013-04-20T22:10:46Z 2013-04-20T22:10:46Z <p>I learned the following proof from Jean-François Mestre, it is a variant of Zolotarev's.</p> <p>For every prime number $p>2$, let $T_p\in\mathbf Z[X]$ be the monic polynomial such that $T_p(X+1/X)X^{(p-1)/2}=(X^p-1)/(X-1)=1+X+\dots+X^{p-1}$. The complex roots of $T_p$ are $x+1/x$, where $x$ is a primitive $p$th root of unity. The same holds in any field of characteristic $\neq p$. In a field of characteristic $p$, the only root of $T_p$ is $2$, with multiplicity $(p-1)/2$.</p> <p>Let $p,q$ be two odd prime numbers, with $p\neq q$.</p> <p>The resultant $\mathop{\rm Res}(T_p,T_q)$ of $T_p$ and $T_q$ is an integer. Since these polynomials have no common root, this integer is non-zero. </p> <p>Since these polynomials have no common root in every field, in particular modulo every prime number, this integer is $\pm1$.</p> <p>Compute this resultant modulo $p$. One gets $\mathop{\rm Res}(T_p,T_q)\equiv (-1)^{(p-1)(q-1)/4} T_q(2)^{(p-1)/2}\equiv (-1)^{(p-1)(q-1)/2} q^{(p-1)/2}\pmod p$. Consequently, $\mathop{\rm Res}(T_p,T_q)=\epsilon \left(\frac qp\right)$, with $\epsilon=(-1)^{(p-1)(q-1)/4}$.</p> <p>Similarly, $\mathop{\rm Res}(T_q,T_p)=\epsilon \left(\frac pq\right)$.</p> <p>Now, $\mathop{\rm Res}(T_p,T_q) = (-1)^{\deg(T_p)\deg(T_q)} \mathop{\rm Res}(T_q,T_p),$ hence the quadratic reciprocity law.</p>