Sunday, April 12, 2020

Some proofs of the quadratic reciprocity law

Gauss's quadratic reciprocity law is a mysterious relation between prime numbers. If pp and qq are distinct prime numbers, it shows that there is a relation between the property that pp is a square modulo qq, and the property that qq is a square modulo pp: both are not independent. Gauss has given many proofs of this law, the first two of them were published in his 1801 Disquisitiones arithmeticae. Franz Lemmermeyer references 246 proofs of the quadratic reciprocity law on his website! In his book Reciprocity laws, from Eisenstein to Kronecker, he adds that “modern number theory dates from the discovery of the reciprocity law” (preface, p. v).

In this post, I want to discuss a few proofs of this law, that will range to the most basic to the most elaborate. But first, the statement.

Stating the quadratic reciprocity law


If pp is an odd prime number, we denote by Fp\mathbf F_p the field with pp elements. In this field, exactly half of the nonzero elements are squares. This is embodied in the following exact sequence of abelian groups:
1  {±1}Fp×aa2Fp×aa(p1)/2{±1}1.1 \to \{\pm1\} \to \mathbf F_p^\times \xrightarrow{a\mapsto a^2} \mathbf F_p^\times \xrightarrow {a\mapsto a^{(p-1)/2}} \{\pm1\} \to 1 .
This means that the image of every morphism is the kernel of the next one. In explicit terms:
  1. Squares are the image of the map aa2a\mapsto a^2 whose kernel is {±1}\{\pm1\};
  2. An element aFp×a\in\mathbf F_p^\times is a square if and only if a(p1)/2=1a^{(p-1)/2}=1; otherwise, a(p1)/2=1a^{(p-1)/2}=-1.
To prove that this is indeed an exact sequence, we work left to right. The kernel of aa2a\mapsto a^2 consists exactly of {±1}\{\pm1\}; the cardinality of the image of this map, the squares,  is thus equal to (p1)/2(p-1)/2. If aFp×a\in\mathbf F_p^\times, one has (a(p1)/2)2=ap1=1(a^{(p-1)/2})^2=a^{p-1}=1, by Fermat's little theorem, so that the image of aa(p1)/2a\mapsto a^{(p-1)/2} is contained in {±1}\{\pm1\}. If aa is a square, writing a=b2a=b^2, one has a(p1)/2=bp1=1a^{(p-1)/2}=b^{p-1}=1, so that the squares are contained in the kernel of this morphism. On the other hand, there are at most (p1)/2(p-1)/2 elements aFp×a\in \mathbf F_p^\times such that a(p1)/2=1a^{(p-1)/2}=1, and the squares account for all of them, so that non squares satisfy a(p1)/2=1a^{(p-1)/2}=-1.

For aFpa\in\mathbf F_p, or even aZa\in\mathbf Z, one classically denotes by (ap)(\frac ap) the element of {0,1,1}\{0,1,-1\} which is equal to expression a(p1)/2a^{(p-1)/2} in Fp\mathbf F_p. This is the Legendre symbol of aa modulo pp.

Let now qq be another odd prime number. We can consider the Legendre symbols (qp)(\frac qp) and (qp)(\frac qp) of qq modulo pp and of pp modulo qq. Thise are elements of {±1}\{\pm1\} and the quadratic reciprocity law states:
(pq)(qp)=(1)(p1)(q1)/4. \big(\frac pq\big) \, \big(\frac qp\big) = (-1)^{(p-1)(q-1)/4}.
Since this may look frightening, let us make this slightly more explicit:
  1. If pp or qq is congruent to 11 modulo 44, then pp is a square modulo qq exactly when qq is a square modulo pp.
  2. If pp and qq both are congruent to 33 modulo 44, then pp is a square modulo qq exactly when qq is not a square modulo pp.
This property may be used to compute Legendre symbols relatively quickly, by successive euclidean divisions.

The complementary laws

A few particular cases are either important, or classical enough to deserve being quoted. They may also have relatively easier proofs which already indicate a relation between the quadratic reciprocity law and roots of unity.

1-1 is a square modulo pp if and only if p1(mod4)p\equiv 1\pmod 4.

Indeed, (1p)=(1)(p1)/2(\frac{-1}p)=(-1)^{(p-1)/2}, which is 11 if and only if (p1)/2(p-1)/2 is even, that is p1(mod4)p\equiv 1\pmod 4. A possibly simple way to understand this is the following: 1-1 is a square in Fp×\mathbf F_p^\times if and only if there are elements of order 44 in Fp×\mathbf F_p^\times, which is equivalent to the divisibility 4p14\mid p-1 because the group Fp×\mathbf F_p^\times is cyclic.

3-3 is a square modulo pp if and only if p1(mod3)p \equiv 1\pmod 3.

Indeed, the usual formula for the cubic roots of unity (1±i3)/2(-1\pm i \sqrt 3)/2 shows that 3-3 is a square modulo pp if and only if there are elements of order 3 in Fp×\mathbf F_p^\times, that is, if and only if 3p13\mid p-1.

33 is a square modulo pp if and only if p±1(mod12)p\equiv \pm1 \pmod{12}.

Indeed, the formula (3p)=(1p)(3p)(\frac 3p)=(\frac{-1}p)(\frac{-3}p) shows that 33 is a square modulo pp if and only if either 3-3 and 1-1 both are squares modulo pp, or both are non-squares modulo pp. The first case holds when p1(mod3)p\equiv 1\pmod 3 and p1(mod4)p\equiv 1\pmod 4, that is, p1(mod12)p\equiv 1\pmod{12}; the second case holds when p1(mod3)p\equiv -1\pmod3 and p1(mod4)p\equiv-1\pmod4, that is, p1(mod12)p\equiv-1\pmod{12}.

22 is a square modulo pp if and only if p±1(mod8)p\equiv \pm1\pmod 8.

We play the same game with octic roots of unity, classically given by (±1+±i)/2(\pm 1+\pm i)/\sqrt 2. So if 1-1 and 22 are squares modulo pp, then there exists an octic root of unity in Fp\mathbf F_p, and p1(mod8)p\equiv 1\pmod 8, and conversely. In the case p1(mod4)p\equiv 1\pmod 4, this show that 22 is a square modulo pp if and only if p1(mod8)p\equiv 1\pmod 8.

On the other hand, one has p21(mod8)p^2\equiv 1\pmod8, whatever odd prime number pp is, so that there exists an octic root of unity ω\omega in the field Fp2\mathbf F_{p^2} with p2p^2 elements. The question is whether ω\omega belongs to Fp\mathbf F_p. This is settled by Fermat's little theorem again: it holds if and only if ωp=ω\omega^p=\omega, equivalently, ωp1=1\omega^{p-1}=1 or p1(mod8)p\equiv 1\pmod 8, and we have not made a single step.

However, if ω=(1+i)/2\omega=(1+i)/\sqrt 2, say, the other octic roots of unity are ω7=ω1=(1i)/2\omega^7=\omega^{-1}=(1-i)/\sqrt 2, ω3=(1+i)/2\omega^3= (-1+i)/\sqrt 2 and ω5=ω=(1+i)/2\omega^5=-\omega=-(1+i)/\sqrt 2, so that 2=ω+ω1\sqrt 2=\omega+\omega^{-1}. Independely of the previous computations, choose an octic root of unity ω\omega and set α=ω+ω1\alpha=\omega+\omega^{-1}. This is an element of Fp2\mathbf F_{p^2} such that α2=ω2+ω2+2=2\alpha^2=\omega^2+\omega^{-2}+2=2 since ω4=1\omega^4=-1. So the question is whether this element α\alpha belongs to Fp\mathbf F_p of not. This can be settled by Fermat's little theorem, and we lead to the conclusion of this complementary law. Indeed αp=ωp+ωp\alpha^p=\omega^p+\omega^{-p} is equal to α\alpha when p±1(mod4)p\equiv \pm1\pmod 4, and to α-\alpha otherwise.

Gauss's lemma and a product formula for the Legendre symbol


Lemma. — (1) Let SFp×S\subset\mathbf F_p^\times be a “half-system” modulo pp, that is, a subset of cardinality (p1)/2(p-1)/2 such that every element of Fp×\mathbf F_p^\times is of the form ±s\pm s for a unique sSs\in S. For aFp×a\in \mathbf F_p^\times, one has  (ap)=(1)m \big( \frac ap \big) = (-1) ^m , where m=Card(aS(S))m=\mathop{\rm Card}( aS \cap (-S)).
(2) Let f ⁣:RC×f\colon \mathbf R\to\mathbf C^\times be an odd 11-periodic function. If p,qp,q are distinct odd prime numbers, then
 (qp)=a=1(p1)/2 f(qa/p)f(a/p). \big( \frac qp\big) = \prod_{a=1}^{(p-1)/2}\frac{ f(qa/p) }{f(a/p)}.


Proof of (1). For sSs\in S, write as=ε(s)saas=\varepsilon(s) s_a, where saSs_a\in S and ε(s){±1}\varepsilon(s)\in\{\pm1\}. The map ssas\mapsto s_a is bijective, so that
 a(p1)/2sSs=sSas=sSε(s)sa=sSε(s)sSsa==sSε(s)sSs. a^{(p-1)/2} \prod_{s\in S} s = \prod_{s\in S} as = \prod_{s\in S} \varepsilon(s) s_a =\prod_{s\in S} \varepsilon(s) \cdot \prod_{s\in S} s_ a= =\prod_{s\in S} \varepsilon(s) \cdot \prod_{s\in S} s.
Simplifying, we get a(p1)/2=sSε(s)a^{(p-1)/2}=\prod_{s\in S}\varepsilon(s). In this product, there are mm factors equal to 1-1, and the other are equal to 11, so that it equals (1)m(-1)^m.

Proof of (2). Since ff is 11-periodic, we may define a function F ⁣:FpC×F\colon \mathbf F_p\to \mathbf C^\times by setting F(α)=f(a/p)F(\alpha)=f(a/p) for every lift aa of α\alpha. Then S={1,,(p1)/2}S=\{1,\dots,(p-1)/2\} is a hals-system modulo pp. It then suffices to compare sSF(qs)\prod_{s\in S} F(qs) and sSF(s)\prod_{s\in S}F(s), similarly as in (1).

Application to the complementary law

The relevance of this lemma to the quadratic reciprocity proof is apparent if one considers the case a=2a=2. Take S={1,,(p1)/2}S=\{1,\dots,(p-1)/2\}. Then, ε(s)=1\varepsilon(s)=1 if s(p1)/4s\leq (p-1)/4 and ε(s)=1\varepsilon(s)=-1 otherwise.
Consequently, m=(p1)/4m=(p-1)/4 if p1(mod4)p\equiv 1\pmod 4, and m=(p+1)/4m=(p+1)/4 if p1(mod4)p\equiv 1\pmod 4, the discrepancy resulting from the thereshold (p1)/4(p-1)/4 for ss being an integer or not. If p1(mod4)p\equiv1\pmod4, this implies (2p)=1(\frac2p)=1 if and only if p1(mod8)p\equiv 1\pmod 8; if p3(mod3)p\equiv 3\pmod3, this implies (2p)=1(\frac2p)=1 if and only if p1(mod8)p\equiv -1\pmod 8.



The proof of Kronecker — or is it Eisenstein? – and some variations


Eisenstein starts from Gauss's lemma with f(x)=sin(2πx)f(x)=\sin(2\pi x). We get
(qp)=a=1(p1)/2sin(2πqa/p)sin(2πa/p).\big( \frac qp\big) = \prod_{a=1}^{(p-1)/2} \frac{\sin(2\pi qa/p)}{\sin(2\pi a/p)}.
On the other hand, for every odd integer qq, there exists a polynomial UqU_q, the Chebyshev polynomial of second kind, such that
sin(qx)=sin(x)Uq(4sin2(x)).\sin (qx) = \sin(x) U_q( 4\sin^2(x) ) .
The relation
\[\sin((q+2)x)+\sin((q-2)x) = 2\sin(qx)\cos(2x)=2\sin(qx)(1-2\cos^2(x))
=2\sin(qx)(1-2\sin^2(x)) \]
shows that
Uq+2(T)+Uq2(T)=(2T)Uq(T).U_{q+2}(T)+U_{q-2}(T) = (2-T)U_q(T).
This recurrence relation is initiated with U1=1U_1=1 and U3=3TU_3=3-T (I'd even take U1=1U_{-1}=-1),
so that UqU_q has integer coefficients, degree (q1)/2(q-1)/2 and its leading coefficient is (1)(q1)/2(-1)^{(q-1)/2}.
Since sin(qx)\sin(qx) vanishes for x=kπ/q(mod2π)x=k\pi/q\pmod{2\pi}, the roots of UqU_q are the 3sin2(kπ/q)3\sin^2(k\pi/q), for 1k(q1)/21\leq k\leq (q-1)/2, and we have the factorization
\[ \sin (qx) = (-1)^{(q-1)/2} \sin(x) \prod_{k=1}^{(q-1)/2} \big( 4\sin^2(x) - 4\sin^2(k\pi/q ) \big)
.\]
Consequently,
\[\big( \frac qp\big) = (-4)^{(q-1)(p-1)/4}
\prod_{a=1}^{(p-1)/2} \prod_{k=1}^{(q-1)/2} \left( \sin ^2(2\pi a/p)- \sin^2(2\pi k/q)\right). \]
By symmetry,
\[ \big( \frac pq\big) = (-4)^{(q-1)(p-1)/4}
\prod_{a=1}^{(q-1)/2} \prod_{k=1}^{(p-1)/2} \left( \sin ^2(2\pi a/q)- \sin^2(2\pi k/p)\right). \]
The big product in the two expressions just differ by the sign of each factor. Consequently,
(pq)=(1)(p1)(q1)/4(qp),\big( \frac pq\big) = (-1)^{(p-1)(q-1)/4} \big( \frac qp\big),
which is the quadratic reciprocity law.

First variation (Kronecker)

The analytic property of the sine function is not really used.
In fact, one can deduce from Gauss's lemma the formula
 (qp)=sign(a=1(p1)/2 k=1(q1)/2(qpkq)). \big(\frac qp\big) = \mathop{\rm sign} \left( \prod_{a=1}^{(p-1)/2} \prod_{k=1}^{(q-1)/2} \big( \frac qp-\frac kq\big)\right) .
This implies the quadratic reciprocity law in a similar way.


Second variation (learnt from Jean-François Mestre)

The products appearing in Eisenstein's proof are reminiscent of resultants. In fact,
one has the following formula:
(qp)=Res(Uq,Up),\big(\frac qp\big) = \mathop{\rm Res}(U_q,U_p),
unless I fucked up the signs.
This equality follows from the analysis above, since the zeroes of UqU_q are 4sin2(kπ/q)4\sin^2(k\pi/q), and those of UpU_p are 4sin2(aπ/p)4\sin^2(a\pi/p), but it can also be proved directly.
Indeed, UpU_p and UqU_q are polynomials with integer coefficients, so that their resultant is an integer. Moreover, the roots of UpU_p are of the form 4sin2(aπ/p)4\sin^2(a\pi/p), but is is better to write them 2(1cos(2aπ/p))=2ωaωa2(1-\cos(2a\pi /p)) = 2-\omega^a-\omega^{-a}, where ω=e2iπ/p\omega=e^{2i\pi/p} is a primitive ppth root of unity. From this, one can observe than UpU_p and UqU_q have no common root, in whatever field of whatever characteristic. Necessarily, their resultant is ±1\pm1. To compute the sign, we compute the resultant modulo pp. Modulo pp, one has Up=(T)(p1)/2U_p=(-T)^{(p-1)/2}, or something like that, and one finds the correct sign.


The proof of Zolotarev — signatures

Lemma (Zolotarev). — For every aFp×a\in\mathbf F_p^\times, the Legendre symbol (ap)(\frac ap) is the signature of the permutation induced by multiplication by aa in Fp\mathbf F_p.

Many proofs are possible. Let ε(a)\varepsilon(a) be this signature. One can use the definition of the signature as (1)(-1) to the number of inversions. This definition implies that
ε(a)=0x<yp1ayaxyx=a(p1)(p2)/2=a(p1)/2 \varepsilon(a)=\prod_{0\leq x<y\leq p-1} \frac{ay - ax}{y-x} = a^{(p-1)(p-2)/2}=a^{(p-1)/2}
since p2p-2 is odd.

On the other hand, the map ε ⁣:Fp×{±1}\varepsilon\colon\mathbf F_p^\times\to\{\pm1\} is a morphism of groups, and the Legendre symbol is the only nontrivial one. If one knows that the group Fp×\mathbf F_p^\times is cyclic, it is enough to understand the case of a generator aa; then multiplication by aa has two orbits, {0}\{0\} and Fp×\mathbf F_p^\times, so that ε(a)=(1)p2=1\varepsilon(a)=(-1)^{p-2}=-1. This proves that ε\varepsilon coincides with the Legendre symbol.

One can also derive Zolotarev's lemma from Gauss's lemma.

This lemma admits many generalizations, such as the following one, classically attributed to Frobenius-Zolotarev in French books for future high school teachers (agrégation). The reference I know of it is the 1970 paper Sur une généralisation des symboles de Legendre et de Jacobi by Pierre Cartier.

Lemma. — Let nn be a positive integer. For gGL(n,Fp)g\in\mathrm{GL}(n,\mathbf F_p) be an invertible matrix, let ε(g)\varepsilon(g) be the permutation of Fpn\mathbf F_p^n induced by gg. One has ε(g)=(det(g)p)\varepsilon(g)=\big( \frac{\det(g)}p\big).

To prove this formula, one can use the fact that ε\varepsilon is a morphism of groups with values in {±1}\{\pm1\}. It is trivial on transvections (because transvections have odd order), hence on the SL(n,Fp)\mathrm{SL}(n,\mathbf F_p) they generate, so that it factors through the determinant. If gg is diagonal (a,1,,1)(a,1,\dots,1), one has det(g)=a\det(g)=a; on the other hand, the orbit of (x1,,xn)(x_1,\dots,x_n) is O(x1)×(x2,,xn)O(x_1)\times (x_2,\dots,x_n), so that it has m1pn1m_1p^{n-1} orbits, m1m_1 being the number of orbits of multiplication by aa on Fp\mathbf F_p. Consequently, ε(g)=(1)pnm1pn1\varepsilon(g)=(-1)^{p^n-m_1p^{n-1}}. Since pn1p^{n-1} is odd, this implies ε(g)=(1)pm1=ε(a)=(ap)\varepsilon(g)=(-1)^{p-m_1}=\varepsilon(a)=(\frac ap) by Zolotarev's lemma.

It must be noted that only two formulas can hold. Since SL(n,Fp)\mathrm{SL}(n,\mathbf F_p) is the derived subgroup of GL(n,Fp)\mathrm{GL}(n,\mathbf F_p), any morphism to a commutative group factors through the determinant, so that there exists a morphism of groups χ ⁣:Fp×{±1}\chi\colon \mathbf F_p^\times\to\{\pm1\} such that ε(g)=χ(det(g))\varepsilon(g)=\chi(\det(g)). But there are only two possibilities of χ\chi:
either χ\chi is the Legendre symbol, or χ=1\chi=1. So it would have been sufficient to find a matrix gGL(n,Fp)g\in\mathrm{GL}(n,\mathbf F_p) such that ε(g)=1\varepsilon(g)=-1 to conclude. This, however, is not so easy — in the same way that it is not so easy to explicitly produce an element of Fp\mathbf F_p which is not a square.


Another proof of the quadratic reciprocity law


In his Nouvelle démonstration de la loi de réciprocité de Legendre, Zolotarev used this lemma to give another proof of Gauss's quadratic reciprocity law. To prove it, one may consider the permutation τ\tau of Z/pqZ\mathbf Z/pq\mathbf Z that maps a+pba+pb to b+qab+qa, for 0a<p0\leq a<p and 0b<q0\leq b<q. Under the identification of Z/pqZ\mathbf Z/pq\mathbf Z with Z/pZ×Z/qZ\mathbf Z/p\mathbf Z\times\mathbf Z/q\mathbf Z provided by the Chinese remainder theorem, this permutation is the composite of two permutations, respectively (x,y)(qx+y,y)(x,y)\mapsto (qx+y,y) and the inverse of (x,y)(x,py+x)(x,y)\mapsto (x,py+x). Using Zolotarev's lemma, one finds that their signatures are (qp)(\frac qp) and (pq)(\frac pq) respectively,
so that ε(τ)=(qp)(pq)\varepsilon(\tau)=(\frac qp )(\frac pq). On the other hand, a+pb<a+pba+pb<a'+pb' if and only if b<bb<b' or b=bb=b' and a<aa< a', so that τ(a+pb)=b+qa\tau(a+pb)=b+qa and τ(a+pb)=b+qa\tau(a'+pb')=b'+q'a give an inversion if and only if b<bb<b' and a>aa>a' or b>bb>b' and a<aa<a'. Taking two pairs (a,a)(a,a'), (b,b)(b,b') of distinct elements, exactly one of the two arrangements a+pb,a+pba+pb, a'+pb' or a+pb,a+pba+pb',a'+pb gives an inversion, so that there are p(p1)/2q(q1)/2p(p-1)/2 \cdot q(q-1)/2 inversions. Since pqpq is odd, this implies ε(τ)=(1)(p1)(q1)/4\varepsilon(\tau)=(-1)^{(p-1)(q-1)/4}.


Signatures and Galois theory

Galois theory furnishes another relation between Zolotarev's lemma and quadratic reciprocity. Let us indeed consider the finite extension Fq E\mathbf F_q\subset  E generated by a primitive ppth root of unity. This is the decomposition extension of the polynomial Tp1T^p-1 over Fq\mathbf F_q. Its Galois group is generated by the map aaqa\mapsto a^q of EE whose action on the ppth roots of unity is exactly the same as multiplication by qq on Z/pZ\mathbf Z/p\mathbf Z. By Zolotarev's lemma, the Galois group is contained in the alternate group of the roots if and only if qq is a square modulo pp. On the other hand, there is a well known criterion for the Galois group of a polynomial to be alternate, namely, that the discriminant of the polynomial is a square. The discriminant of Tp1T^p-1 is classically computed as (1)p(p1)/2pp (1)p1=(1)(p1)/2ppp1(-1)^{p(p-1)/2} p^p  (-1)^{p-1}=(-1)^{(p-1)/2}p \cdot p^{p-1} since pp is odd. This proves that (qp)=1(\frac qp)=1 if and only if (1)(p1)/2p(-1)^{(p-1)/2}p is a square in Fq\mathbf F_q, in other words,
(qp)=((1)(p1)/2p)(q1)/2=(1)(p1)(q1)/4(pq), \big( \frac qp\big) = \left( (-1)^{(p-1)/2} p \right)^{(q-1)/2} = (-1)^{(p-1)(q-1)/4} \big( \frac pq\big),
which proves once again the quadratic reciprocity law.


Proofs via Gauss sums

Let ω\omega be a primitive nnth root of unity in some field KK. The Gauss sums are the expressions
 G(ω)=a=1n1ωa2. G(\omega)=\sum_{a=1}^{n-1} \omega^{a^2}.
If n=pn=p is a prime number, then this can be rewritten as follows, using the fact that the sum of all ppth roots of unity vanishes:
G(ω)=a=0p1(ap)ωa. G(\omega)=\sum_{a=0}^{p-1} \big(\frac ap\big) \omega^{a}.
The following computation is of the same spirit as the computation done with octic roots of unity (except for the minor fact that 88 is not an odd prime number).

Lemma. — One has G(ω)2=(1)(p1)/2pG(\omega)^2=(-1)^{(p-1)/2} p.

This starts by a direct computation:
\[ G(\omega)^2=\sum_{a,b\in\mathbf F_p} \big(\frac ap\big) \big(\frac bp\big) \omega^{a+b}
= \sum_{x\in\mathbf F_p} \sum_{a\in\mathbf F_p} \big( \frac{a(x-a)}p\big) \omega^x. \]
Fix xFpx\in\mathbf F_p.
If x=0x=0, then one has (a(xa)p)=(a2p)=(1)(p1)/2(\frac{a(x-a)}p)=(\frac{-a^2}p)=(-1)^{(p-1)/2} for every aa, and the coefficient of ωx\omega^x is thus (1)(p1)/2p(-1)^{(p-1)/2}p.
Assume x0x\neq0. a0a\neq 0, one has a(xa)=a2(1x/a)a(x-a)=-a^2(1-x/a), hence
 (a(xa)p)=(1)(p1)/2(1x/ap) \big(\frac{a(x-a)}p\big)=(-1)^{(p-1)/2} \big( \frac{1-x/a}p\big)
and when aa varies, 1x/a1-x/a takes all values in Fp\mathbf F_p but 11. Would it take all values, the sum of all (1x/ap)(\frac{1-x/a}p) would be zero, because there are as many squares as non squares, and 00 does not count, so that the sum is 1-1. This gives
\[ G(\omega)^2=(-1)^{(p-1)/2}p - (-1)^{(p-1)/2} \sum_{x\in\mathbf F_p^\times} \omega^x
= (-1)^{(p-1)/2}p \]
because the sum of all non-trivial ppth roots of unity vanishes.


Proving quadratic reciprocity via finite fields

One way to prove quadratic reciprocity from there is to take for KK a finite extension of Fq\mathbf F_q, the second prime number. One then has
\[ G(\omega)^q = \sum_{a=0}^{p-1} \big( \frac ap\big)^q \omega^{aq}
= \sum_{b=0}^{p-1} \big(\frac{b/q}p\big) \omega^b , \]
using the change of variables b=aqb=aq. Since (b/qp)=(bp)q(p1)/2(\frac{b/q}p\big)=(\frac bp) q^{(p-1)/2}, we get
 G(ω)q=q(p1)/2 b=0p1(bp)ωb=(qp)G(ω), G(\omega)^q = q^{(p-1)/2} \sum_{b=0}^{p-1} \big(\frac bp\big) \omega^b = \big(\frac qp\big) G(\omega),
and
 G(ω)q1=(qp). G(\omega)^{q-1} = \big( \frac qp\big).
Combining this result with the previous lemma, it follows that
 ((1)(p1)/2 p)(q1)/2=(qp), \left( (-1)^{(p-1)/2} p \right)^{(q-1)/2} = \big( \frac qp \big),
which implies quadratic reciprocity after some straightforward manipulations.


Proving quadratic reciprocity via complex numbers

Another way to prove quadratic reciprocity is to choose a specific root of unity in C\mathbf C, namely ω=e2iπ/n\omega=e^{2i\pi/n}. If n=pn=p is an odd prime number, then G(ω)2=(1)(p1)/2pG(\omega)^2=(-1)^{(p-1)/2}p has two roots in C\mathbf C, and one needs to identify which of them G(ω)G(\omega) is. Determining the sign of the Gauss sum proved to be a much more difficult problem, and Gauss proved it only later.

Theorem. — One has Gn=nG_n=\sqrt n, 00, ini\sqrt n, (1+i)n(1+i)\sqrt n according to n0,1,2,3(mod4)n\equiv 0, 1, 2, 3\pmod 4.

Writing any integer in {1,,pq}\{1,\dots,pq\} as py+qxpy+qx, with x{1,,p}x\in\{1,\dots,p\} and y{1,,q}y\in\{1,\dots,q\}, one can prove that Gpq=GpGq(qp)(pq)G_{pq}=G_pG_q (\frac qp)(\frac pq). Given the explicit value for Gp,GqG_p,G_q and GpqG_{pq}, this implies the quadratic reciprocity law.