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 is an odd prime number, we denote by the field with elements. In this field, exactly half of the nonzero elements are squares. This is embodied in the following exact sequence of abelian groups:
This means that the image of every morphism is the kernel of the next one. In explicit terms:
- Squares are the image of the map whose kernel is ;
- An element is a square if and only if ; otherwise, .
For , or even , one classically denotes by the element of which is equal to expression in . This is the Legendre symbol of modulo .
Let now be another odd prime number. We can consider the Legendre symbols and of modulo and of modulo . Thise are elements of and the quadratic reciprocity law states:
Since this may look frightening, let us make this slightly more explicit:
- If or is congruent to modulo , then is a square modulo exactly when is a square modulo .
- If and both are congruent to modulo , then is a square modulo exactly when is not a square modulo .
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.is a square modulo if and only if .
Indeed, , which is if and only if is even, that is . A possibly simple way to understand this is the following: is a square in if and only if there are elements of order in , which is equivalent to the divisibility because the group is cyclic.is a square modulo if and only if .
Indeed, the usual formula for the cubic roots of unity shows that is a square modulo if and only if there are elements of order 3 in , that is, if and only if .is a square modulo if and only if .
Indeed, the formula shows that is a square modulo if and only if either and both are squares modulo , or both are non-squares modulo . The first case holds when and , that is, ; the second case holds when and , that is, .is a square modulo if and only if .
We play the same game with octic roots of unity, classically given by . So if and are squares modulo , then there exists an octic root of unity in , and , and conversely. In the case , this show that is a square modulo if and only if .On the other hand, one has , whatever odd prime number is, so that there exists an octic root of unity in the field with elements. The question is whether belongs to . This is settled by Fermat's little theorem again: it holds if and only if , equivalently, or , and we have not made a single step.
However, if , say, the other octic roots of unity are , and , so that . Independely of the previous computations, choose an octic root of unity and set . This is an element of such that since . So the question is whether this element belongs to of not. This can be settled by Fermat's little theorem, and we lead to the conclusion of this complementary law. Indeed is equal to when , and to otherwise.
Gauss's lemma and a product formula for the Legendre symbol
Lemma. — (1) Let be a “half-system” modulo , that is, a subset of cardinality such that every element of is of the form for a unique . For , one has , where .
(2) Let be an odd -periodic function. If are distinct odd prime numbers, then
Proof of (1). For , write , where and . The map is bijective, so that
Simplifying, we get . In this product, there are factors equal to , and the other are equal to , so that it equals .
Proof of (2). Since is -periodic, we may define a function by setting for every lift of . Then is a hals-system modulo . It then suffices to compare and , 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 . Take . Then, if and otherwise.Consequently, if , and if , the discrepancy resulting from the thereshold for being an integer or not. If , this implies if and only if ; if , this implies if and only if .
The proof of Kronecker — or is it Eisenstein? – and some variations
Eisenstein starts from Gauss's lemma with . We get
On the other hand, for every odd integer , there exists a polynomial , the Chebyshev polynomial of second kind, such that
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
This recurrence relation is initiated with and (I'd even take ),
so that has integer coefficients, degree and its leading coefficient is .
Since vanishes for , the roots of are the , for , 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,
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
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:
unless I fucked up the signs.
This equality follows from the analysis above, since the zeroes of are , and those of are , but it can also be proved directly.
Indeed, and are polynomials with integer coefficients, so that their resultant is an integer. Moreover, the roots of are of the form , but is is better to write them , where is a primitive th root of unity. From this, one can observe than and have no common root, in whatever field of whatever characteristic. Necessarily, their resultant is . To compute the sign, we compute the resultant modulo . Modulo , one has , or something like that, and one finds the correct sign.
The proof of Zolotarev — signatures
Lemma (Zolotarev). — For every , the Legendre symbol is the signature of the permutation induced by multiplication by in .
Many proofs are possible. Let be this signature. One can use the definition of the signature as to the number of inversions. This definition implies that
since is odd.
On the other hand, the map is a morphism of groups, and the Legendre symbol is the only nontrivial one. If one knows that the group is cyclic, it is enough to understand the case of a generator ; then multiplication by has two orbits, and , so that . This proves that 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 be a positive integer. For be an invertible matrix, let be the permutation of induced by . One has .
To prove this formula, one can use the fact that is a morphism of groups with values in . It is trivial on transvections (because transvections have odd order), hence on the they generate, so that it factors through the determinant. If is diagonal , one has ; on the other hand, the orbit of is , so that it has orbits, being the number of orbits of multiplication by on . Consequently, . Since is odd, this implies by Zolotarev's lemma.
It must be noted that only two formulas can hold. Since is the derived subgroup of , any morphism to a commutative group factors through the determinant, so that there exists a morphism of groups such that . But there are only two possibilities of :
either is the Legendre symbol, or . So it would have been sufficient to find a matrix such that to conclude. This, however, is not so easy — in the same way that it is not so easy to explicitly produce an element of 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 of that maps to , for and . Under the identification of with provided by the Chinese remainder theorem, this permutation is the composite of two permutations, respectively and the inverse of . Using Zolotarev's lemma, one finds that their signatures are and respectively,
so that . On the other hand, if and only if or and , so that and give an inversion if and only if and or and . Taking two pairs , of distinct elements, exactly one of the two arrangements or gives an inversion, so that there are inversions. Since is odd, this implies .
Signatures and Galois theory
Galois theory furnishes another relation between Zolotarev's lemma and quadratic reciprocity. Let us indeed consider the finite extension generated by a primitive th root of unity. This is the decomposition extension of the polynomial over . Its Galois group is generated by the map of whose action on the th roots of unity is exactly the same as multiplication by on . By Zolotarev's lemma, the Galois group is contained in the alternate group of the roots if and only if is a square modulo . 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 is classically computed as since is odd. This proves that if and only if is a square in , in other words,
which proves once again the quadratic reciprocity law.
Proofs via Gauss sums
Let be a primitive th root of unity in some field . The Gauss sums are the expressions
If is a prime number, then this can be rewritten as follows, using the fact that the sum of all th roots of unity vanishes:
The following computation is of the same spirit as the computation done with octic roots of unity (except for the minor fact that is not an odd prime number).
Lemma. — One has .
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 .
If , then one has for every , and the coefficient of is thus .
Assume . , one has , hence
and when varies, takes all values in but . Would it take all values, the sum of all would be zero, because there are as many squares as non squares, and does not count, so that the sum is . 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 th roots of unity vanishes.
Proving quadratic reciprocity via finite fields
One way to prove quadratic reciprocity from there is to take for a finite extension of , 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 . Since , we get
and
Combining this result with the previous lemma, it follows that
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 , namely . If is an odd prime number, then has two roots in , and one needs to identify which of them 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 , , , according to .
Writing any integer in as , with and , one can prove that . Given the explicit value for and , this implies the quadratic reciprocity law.