Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues
We define the Legendre symbol, prove Euler's criterion, and establish Gauss's lemma. We then prove the law of quadratic reciprocity and discuss the Jacobi symbol and the Tonelli--Shanks algorithm for computing square roots modulo primes.
1 Quadratic Residues
Definition 1 (Quadratic residue).
Let be an odd prime and an integer with . If the congruence has a solution, then is called a quadratic residue modulo . Otherwise, is a quadratic non-residue modulo .
Definition 2 (Legendre symbol).
For an odd prime and an integer , the Legendre symbol is defined by
Theorem 3.
Among , exactly are quadratic residues modulo and exactly are quadratic non-residues.
Proof.
Define by . We have if and only if , equivalently . Thus each quadratic residue is the image of exactly two elements, so the number of quadratic residues is . □
2 Euler's Criterion
Theorem 4 (Euler's criterion).
For an odd prime and an integer with ,
Proof.
If is a quadratic residue, say , then by Fermat's little theorem. The polynomial has degree over and therefore at most roots; the quadratic residues account for all of them. Hence if and only if is a quadratic residue. Since , we have , so . For a quadratic non-residue, we conclude . □
3 Gauss's Lemma
Lemma 5 (Gauss's lemma).
Let be an odd prime and . Among the residues of reduced to representatives in , let denote the number of negative representatives. Then
Proof.
Let be the reduced representatives. Their absolute values form a permutation of . (If with , then , giving or ; the latter is impossible since .) Hence , while . Dividing both sides by yields . The result now follows from Euler's criterion. □
4 The First Supplement to Quadratic Reciprocity
Theorem 6 (First supplement).
For an odd prime ,
In other words, is a quadratic residue modulo if and only if .
Proof.
By Euler's criterion, . Since and (so ), the congruence holds as an equality of integers. When , the exponent is even, giving . When , the exponent is odd, giving . □
5 The Law of Quadratic Reciprocity
Theorem 7 (Quadratic reciprocity).
For distinct odd primes ,
Proof.
Using Gauss's lemma, we write and reduce the count to a lattice-point enumeration. Consider the rectangle . The number of negative representatives of equals the number of lattice points below the line that lie in a certain complementary region. A symmetric argument applies to , where . Combining yields , and therefore . □
6 The Jacobi Symbol
Definition 8 (Jacobi symbol).
For an odd positive integer (where the are odd primes, not necessarily distinct), the Jacobi symbol is defined as .
Remark 9.
The Jacobi symbol inherits the reciprocity law and can be computed efficiently in time without factoring . One must note, however, that does not in general imply that is a quadratic residue modulo .
7 The Tonelli–Shanks Algorithm
Remark 10.
When is a quadratic residue modulo a prime , the Tonelli–Shanks algorithm finds a solution to . It factors with odd, selects a quadratic non-residue , and iteratively constructs the solution. The running time is .
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 フォロワー·105 記事