In number theory, the quadratic reciprocity law determines a precise relationship between the truth of and the truth of , where is this binary relation on odd prime numbers: “ is a square modulo ”.
The law of quadratic reciprocity is a celebrated result due to Gauss; the ideas required to prove it helped to inaugurate modern number theory. It is today largely considered within the context of class field theory, involving how primes decompose in abelian extensions of number fields.
For an odd prime number, and for any integer , define the Legendre symbol (or quadratic reciprocity symbol) to be the unique element in for which
Notice that the Legendre symbol defines a surjective homomorphism on a cyclic group
whose kernel is the set of squares in the multiplicative group , so that means is a square modulo , and means is a non-square modulo .
For , distinct odd primes,
i.e., is a square modulo if and only if .
The case for odd primes , can be restated as:
if are odd and , then
if then
The law of quadratic reciprocity was first fully proven by Gauss, although special cases were proven by Fermat (who effectively realized when was a square modulo based on his two squares theorem? – well before Legendre introduced his eponymous symbol), and Euler (who proved the case for ).
None of these early authors were in full possession of modern notations such as the congruence symbol or the Legendre symbol, which greatly economize the amount of thought needed to prove this theorem. Recognition of quadratic reciprocity was likely rooted in empirical observations, for example the study of periods of expansions of in base (source?).
Consider the problem of computing the length of the period of in its decimal expansion. This period is the same as the least positive exponent such that , and is a divisor of (thus, a power of ). Indeed, is a Fermat prime: .
The period is a proper divisor of if and only if is a square modulo , leading one to contemplate
where the first factor is pretty clearly (already , so certainly ). The other factor is
and we therefore conclude is a non-square modulo , or in other words that the length of the period of is .
There are today several hundred published proofs of the quadratic reciprocity laws; it is rightly regarded as a capstone result in introductions to number theory. We give two proofs here.
This proof, following Lang (pp. 76–78), is middling in sophistication but at least indicates the relevance of cyclotomic extensions of the rationals and quadratic extension?s therein. Let be a fixed odd prime, and let be a primitive root of unity. Using the Legendre symbol, we introduce a particular character sum called a Gauss sum?,
where the sum is over non-zero elements of .
.
We have . For any fixed non-zero , as ranges over all non-zero residue classes, so does . We may therefore replace by to get
Now, for , the character sum evaluates to since . Thus the calculation continues:
which completes the proof.
Thus belongs to a quadratic extension of , either or depending on the Legendre symbol. In particular, the prime is ramified in .
First let , be two distinct odd primes. With defined as above, we calculate , where indicates the quotient of the ideal generated by in the above-mentioned quadratic extension of , in two ways.
On the one hand, by the preceding lemma,
On the other hand, since raising to the power is an automorphism on the quotient ring obtained modulo (either or , depending on whether is a square modulo or not), we have
and now we can cancel (which is invertible modulo , since is) to arrive at
which gives the first clause of the reciprocity law.
As for the second clause, we can give a similar analysis. The prime is ramified in the cyclotomic extension since , and for any prime we may calculate in two ways. On the one hand,
and on the other hand,
and by examining the cases separately, we easily deduce the second clause.
The (in hindsight obvious!) structural meaning of the Legendre symbol was first given by Zolotarev:
For an odd prime and relatively prime to , is the sign or signature of a permutation on given by multiplying by .
Both the Legendre symbol and
are homomorphisms whose domain is a cyclic group, so it suffices to show they agree on a generator . But is a cyclic permutation on elements, hence has sign , which agrees with .
We turn now to Zolotarev’s proof of the “hard” case of quadratic reciprocity where and are distinct odd primes. What is interesting is that from this point forward, we don’t use primality of and at all, i.e., the remainder of the argument carries over if and are replaced by odd, relatively prime integers and , and we simply define as a sign of a permutation of multiplying by on . Indeed, one often defines the Jacobi symbol by
where is the prime factorization of an odd integer, and what we really do is generalize quadratic reciprocity from the Legendre symbol to the Jacobi symbol. Thus, the primality assumption is concentrated purely in the preceding lemma.
For an odd number, we consider the set as carrying on the one hand a ring structure, and on the other as carrying a structure of linear order (no compatibility between these structures!). Now suppose and are odd and relatively prime; then by the Chinese remainder theorem?, there is a unique ring isomorphism
If we endow with the dictionary or lexicographic order, then there is also a unique isomorphism of linear or total orders
which takes an element to . (Intuitively, imagine assembling a rectangular array of cards, with columns and cards in each column, into a single stack of cards, by gathering up the first column, followed by gathering up the second column and placing it underneath, etc.)
The composite of the functions
is thus . The composite is thus a juxtaposition of row permutations, one for each fixed , where in row is taken to in row . The sign of such a permutation is
(since the permutation is a cyclic permutation on an odd number of elements, hence is even). Thus
where the second equation follows since is odd.
Similarly, consider with the reverse dictionary order, where if or and . We again have a unique order isomorphism and unique ring isomorphism, and we can analyze their composition ,
as taking . We similarly calculate
Finally, is the unique order-preserving isomorphism
which gives a permutation on the underlying set , and it remains to show that its sign is .
But this is easy to see. Recall that given a permutation on a linearly ordered set (such as ), an inversion is a pair such that , and if is the total number of inversions, then
In the present case , we see counts pairs of pairs , where in dictionary order but in reverse dictionary order; in other words when but . The number of such occurrences is
whence (again since are odd)
which completes the proof.
As mentioned earlier, quadratic reciprocity law is due to Gauss and is the first of a number of reciprocity laws in number theory. The Wikipedia article lists a bevy of reciprocity laws, gradually increasing in modernity and abstraction (and power), and culminating in Artin reciprocity, a capstone of the classical class field theory.
wikipedia: reciprocity laws (mathematics)
Serge Lang, Algebraic number theory, Addison-Wesley (1970).
Carl Friedrich Gauss, Disquisitiones arithmeticae (1801), Article IV.
E.I. Zolotareff, Nouvelle démonstration de la loi de de réciprocité de Legendre, Nouvelles Annales de Mathématiques. 2e série 11 (1872) 354–362.
Last revised on March 29, 2017 at 13:34:23. See the history of this page for a list of all contributions to it.