trigonometry & functions |
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics
Related Links (Outside this Site)Schauspiel about the third proof by Gauss of the law of quadratic reciprocity.
More than 200 proofs of the quadratic reciprocity law.
Reciprocity Laws: from Euler to Eisenstein by Franz Lemmermeyer
Euler conjectured that, for any prime q, any prime factor p of n2-q (besides, possibly, p=2 and p=q) must be of the form 4qk+b2 or 4qk-b2 for some odd integer b. That's the earliest statement of the law of quadratic reciprocity.
Although special cases had been noted by Euler and Lagrange, the fully general theorem is credited to Legendre, who devised a special notation to express it.
More than a hundred proofs of this deep result have been tallied. Carl Friedrich Gauß found the first of these in 1795 and published it in Section 4 of Disquisitiones Arithmeticae (1796). He came up with no fewer than 8 different proofs over his lifetime. None of these truly satisfied him, though... Apparently, the multitude of proofs serves only to increase the mystery shrouding the law of quadratic reciprocity, which Gauß dubbed Aureum Theorema (the golden theorem). The following articles present this golden topic, which once stirred the enthusiasm of the great Gauss.
Modulo an odd prime, half the nonzero residues are squares.
A quadratic residue is simply the congruence class of a square. The term is usually reserved to nonzero residues. By contrast, a residue which is not congruent to any square is sometimes called a quadratic nonresidue [sic].
Modulo an odd prime p, there are just (p-1)/2 quadratic residues, namely:
12, 22, ... [(p-1)/2]2 (modulo p)
Those are all distinct because the residue ring / p is known to be a field (a finite ring can be proven to be a field if there are no divisors of zero in it). In a field, x and y have the same square if and only if
(x-y) (x+y) = 0
This implies that y is either x or -x (these two are distinct, since the field at hand is not of characteristic 2). The opposite of a residue x being of the form p-x, the above does enumerate all the quadratic residues modulo p.
How to tell whether a given residue is congruent to a square.
Leonhard Euler (1707-1783) devised the first effective test to tell quickly whether a given residue is a quadratic residue or not. This is known as Euler's criterion : Modulo an odd prime p, the nonzero residue a is a quadratic residue if and only if the following equation is true, modulo p :
a (p-1)/2 = 1
This is easily established by considering a primitive root g (i.e., a residue generating multiplicatively the group of the p-1 nonzero residues modulo p). The even powers of g are quadratic residues and the odd powers are not.
In particular, g itself can't be a quadratic residue (the order of g must be p-1, and it would be at most (p-1)/2 if g was congruent to the square of some x, since the order of x divides p-1, by Fermat's little theorem).
If a is an even power of g , the above relation holds (as the left-hand side is something raised to the power of p-1). Conversely, if a is an odd power of g, then the left-hand side is congruent to g raised to (p-1)/2 which must be congruent to -1 (as it can't be congruent to 1 while its square is).
The original definition was generalized by Jacobi and Kronecker.
Part of the secret of analysis is the art of using notations well.
Original definition, by Adrien-Marie Legendre (1752-1833)
At first, the Legendre symbol (a|p)
was defined as follows,
For obvious typographical reasons, we use the "horizontal" version (a|p) of the symbol, although the more traditional "vertical" version is preferred in print.
Euler's criterion, as discussed above, may thus be simply expressed:
If p is an odd prime, then (a|p) = a (p-1)/2 (modulo p).
The Legendre symbol was introduced specifically to stress the nice symmetrical relationship between (m|n) and (n|m) when m and n are both odd primes. This relation (the very law of quadratic reciprocity) is expressed by the last two of the following fundamental properties of the Legendre symbol :
[ Skip the rest of this article on first reading. ]
It was later realized that it could be useful to consistently define the meaning of the symbol for less restricted arguments, while maintaining the above properties.
Although it's traditionally done, there's no compelling reason to call a generalized version of the Legendre symbol by any other name... The Jacobi symbol and Kronecker symbol are just to the restricted Legendre symbol what real and complex exponents are to integral exponents [ for a positive base, of course ].
Generalization, by Karl Gustav Jacobi (1804-1851)
Jacobi has defined (a|k) for any odd integer k by adding the simple rule:
Further generalization, by Leopold Kronecker (1823-1891)
Kronecker proposed to define the symbol for all integers by adding the rules:
Some authors argue that the above needlessly defines the symbol (n|2) when n is congruent to 2, 3, 6 or 7 modulo 8. They'd rather leave such cases undefined.
Shuning later generalizations, this law states a simple but surprising fact:
For two distinct odd primes p and q, the following statements are either both true or both false, unless p and q are both congruent to 3 modulo 4, in which case one statement is true and the other is not:
The Legendre symbol (a|p) is the product of (p-1)/2 signs.
For a given odd prime p, let's denote < a > the integer congruent to a which is between -p/2 and +p/2. Gauss' lemma states that
Proof : Since the result is trivial when p divides a (the sign of 0 being 0) we may assume that a is invertible modulo p.
The absolute values | < j a > | are all distinct, since a is invertible modulo p [otherwise, distinct values of j would be either equal or opposite modulo p, which is ruled out in the range from 1 to (p-1)/2]. These absolute values thus assume all the values from 1 to (p-1)/2, once and only once (the pigeonhole principle ) and their product F is the factorial of (p-1)/2. Therefore, (using Euler's criterion) we have the following equalities, modulo p:
Proposed in 1844 to simplify the 1808 third proof of Gauss.
The idea and the result are similar to Gauss's lemma, except that the nonzero residues (modulo an odd prime p) are split into even and odd ones, instead of being split into low and high ones, as in Gauss' original lemma.
If r is the (least positive) remainder of ja modulo p, then (-1)r r has an even least positive remainder modulo p
A modern proof based on Gauss' Lemma.
To use Gauss' lemma when a is between 1 and p-1, we may use the following pseudocode to count the number of times k for which x = < j a > is negative:
x := 0 ; k := 0 ;
A generalization due to Emil Artin (1898-1962).
Artin's Reciprocity and Mersenne Primes (pdf) by H.W. Lenstra Jr. and P. Stevenhagen (March 2000).