In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:
This law, together with its supplements, allows the easy calculation of any Legendre symbol, making it possible to determine whether there is an integer solution for any quadratic equation of the form x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} for an odd prime p {\displaystyle p} ; that is, to determine the "perfect squares" modulo p {\displaystyle p} . However, this is a non-constructive result: it gives no help at all for finding a specific solution; for this, other methods are required. For example, in the case p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3{\pmod {4}}} using Euler's criterion one can give an explicit formula for the "square roots" modulo p {\displaystyle p} of a quadratic residue a {\displaystyle a} , namely,
± a p + 1 4 {\displaystyle \pm a^{\frac {p+1}{4}}}
indeed,
( ± a p + 1 4 ) 2 = a p + 1 2 = a ⋅ a p − 1 2 ≡ a ( a p ) = a ( mod p ) . {\displaystyle \left(\pm a^{\frac {p+1}{4}}\right)^{2}=a^{\frac {p+1}{2}}=a\cdot a^{\frac {p-1}{2}}\equiv a\left({\frac {a}{p}}\right)=a{\pmod {p}}.}
This formula only works if it is known in advance that a {\displaystyle a} is a quadratic residue, which can be checked using the law of quadratic reciprocity. The quadratic reciprocity theorem was conjectured by Leonhard Euler and Adrien-Marie Legendre and first proved by Carl Friedrich Gauss, who referred to it as the "fundamental theorem" in his Disquisitiones Arithmeticae and his papers, writing
The fundamental theorem must certainly be regarded as one of the most elegant of its type. (Art. 151) Privately, Gauss referred to it as the "golden theorem". He published six proofs for it, and two more were found in his posthumous papers. There are now over 240 published proofs. The shortest known proof is included below, together with short proofs of the law's supplements (the Legendre symbols of −1 and 2). Generalizing the reciprocity law to higher powers has been a leading problem in mathematics, and has been crucial to the development of much of the machinery of modern algebra, number theory, and algebraic geometry, culminating in Artin reciprocity, class field theory, and the Langlands program.
Motivating examples Quadratic reciprocity arises from certain subtle factorization patterns involving perfect square numbers. In this section, we give examples which lead to the general case.
Factoring n2 − 5 Consider the polynomial f ( n ) = n 2 − 5 {\displaystyle f(n)=n^{2}-5} and its values for n ∈ N . {\displaystyle n\in \mathbb {N} .} The prime factorizations of these values are given as follows:
The prime factors p {\displaystyle p} dividing f ( n ) {\displaystyle f(n)} are p = 2 , 5 {\displaystyle p=2,5} , and every prime whose final digit is 1 {\displaystyle 1} or 9 {\displaystyle 9} ; no primes ending in 3 {\displaystyle 3} or 7 {\displaystyle 7} ever appear. Now, p {\displaystyle p} is a prime factor of some n 2 − 5 {\displaystyle n^{2}-5} whenever n 2 − 5 ≡ 0 ( mod p ) {\displaystyle n^{2}-5\equiv 0{\pmod {p}}} , i.e. whenever n 2 ≡ 5 ( mod p ) , {\displaystyle n^{2}\equiv 5{\pmod {p}},} i.e. whenever 5 is a quadratic residue modulo p {\displaystyle p} . This happens for p = 2 , 5 {\displaystyle p=2,5} and those primes with p ≡ 1 , 4 ( mod 5 ) , {\displaystyle p\equiv 1,4{\pmod {5}},} and the latter numbers 1 = ( ± 1 ) 2 {\displaystyle 1=(\pm 1)^{2}} and 4 = ( ± 2 ) 2 {\displaystyle 4=(\pm 2)^{2}} are precisely the quadratic residues modulo 5 {\displaystyle 5} . Therefore, except for p = 2 , 5 {\displaystyle p=2,5} , we have that 5 {\displaystyle 5} is a quadratic residue modulo p {\displaystyle p} iff p {\displaystyle p} is a quadratic residue modulo 5 {\displaystyle 5} . The law of quadratic reciprocity gives a similar characterization of prime divisors of f ( n ) = n 2 − q {\displaystyle f(n)=n^{2}-q} for any prime q, which leads to a characterization for any integer q {\displaystyle q} .
Patterns among quadratic residues Let p be an odd prime. A number modulo p is a quadratic residue whenever it is congruent to a square (mod p); otherwise it is a quadratic non-residue. ("Quadratic" can be dropped if it is clear from the context.) Here we exclude zero as a special case. Then as a consequence of the fact that the multiplicative group of a finite field of order p is cyclic of order p-1, the following statements hold:
There are an equal number of quadratic residues and non-residues; and The product of two quadratic residues is a residue, the product of a residue and a non-residue is a non-residue, and the product of two non-residues is a residue. For the avoidance of doubt, these statements do not hold if the modulus is not prime. For example, there are only 3 quadratic residues (1, 4 and 9) in the multiplicative group modulo 15. Moreover, although 7 and 8 are quadratic non-residues, their product 7x8 = 11 is also a quadratic non-residue, in contrast to the prime case. Quadratic residues appear as entries in the following table, indexed by the row number as modulus and column number as root:
This table is complete for odd primes less than 50. To check whether a number m is a quadratic residue mod one of these primes p, find a ≡ m (mod p) and 0 ≤ a < p. If a is in row p, then m is a residue (mod p); if a is not in row p of the table, then m is a nonresidue (mod p). The quadratic reciprocity law is the statement that certain patterns found in the table are true in general.
Legendre's version Another way to organize the data is to see which primes are quadratic residues mod which other primes, as illustrated in the following table. The entry in row p column q is R if q is a quadratic residue (mod p); if it is a nonresidue the entry is N. If the row, or the column, or both, are ≡ 1 (mod 4) the entry is blue or green; if both row and column are ≡ 3 (mod 4), it is yellow or orange. The blue and green entries are symmetric around the diagonal: The entry for row p, column q is R (resp N) if and only if the entry at row q, column p, is R (resp N). The yellow and orange ones, on the other hand, are antisymmetric: The entry for row p, column q is R (resp N) if and only if the entry at row q, column p, is N (resp R). The reciprocity law states that these patterns hold for all p and q.
Ordering the rows and columns mod 4 makes the pattern clearer.
Supplements to quadratic reciprocity The supplements provide solutions to specific cases of quadratic reciprocity. They are often quoted as partial results, without having to resort to the complete theorem.
q = ±1 and the first supplement Trivially 1 is a quadratic residue for all primes. The question becomes more interesting for −1. Examining the table, we find −1 in rows 5, 13, 17, 29, 37, and 41 but not in rows 3, 7, 11, 19, 23, 31, 43 or 47. The former set of primes are all congruent to 1 modulo 4, and the latter are congruent to 3 modulo 4.
First Supplement to Quadratic Reciprocity. The congruence x 2 ≡ − 1 ( mod p ) {\displaystyle x^{2}\equiv -1{\pmod {p}}} is solvable if and only if p {\displaystyle p} is congruent to 1 modulo 4.
q = ±2 and the second supplement Examining the table, we find 2 in rows 7, 17, 23, 31, 41, and 47, but not in rows 3, 5, 11, 13, 19, 29, 37, or 43. The former primes are all ≡ ±1 (mod 8), and the latter are all ≡ ±3 (mod 8). This leads to
Second Supplement to Quadratic Reciprocity. The congruence x 2 ≡ 2 ( mod p ) {\displaystyle x^{2}\equiv 2{\pmod {p}}} is solvable if and only if p {\displaystyle p} is congruent to ±1 modulo 8. −2 is in rows 3, 11, 17, 19, 41, 43, but not in rows 5, 7, 13, 23, 29, 31, 37, or 47. The former are ≡ 1 or ≡ 3 (mod 8), and the latter are ≡ 5, 7 (mod 8).
q = ±3 3 is in rows 11, 13, 23, 37, and 47, but not in rows 5, 7, 17, 19, 29, 31, 41, or 43. The former are ≡ ±1 (mod 12) and the latter are all ≡ ±5 (mod 12). −3 is in rows 7, 13, 19, 31, 37, and 43 but not in rows 5, 11, 17, 23, 29, 41, or 47. The former are ≡ 1 (mod 3) and the latter ≡ 2 (mod 3). Since the only residue (mod 3) is 1, we see that −3 is a quadratic residue modulo every prime which is a residue modulo 3.
q = ±5 5 is in rows 11, 19, 29, 31, and 41 but not in rows 3, 7, 13, 17, 23, 37, 43, or 47. The former are ≡ ±1 (mod 5) and the latter are ≡ ±2 (mod 5). Since the only residues (mod 5) are ±1, we see that 5 is a quadratic residue modulo every prime which is a residue modulo 5. −5 is in rows 3, 7, 23, 29, 41, 43, and 47 but not in rows 11, 13, 17, 19, 31, or 37. The former are ≡ 1, 3, 7, 9 (mod 20) and the latter are ≡ 11, 13, 17, 19 (mod 20).
Higher q The observations about −3 and 5 continue to hold: −7 is a residue modulo p if and only if p is a residue modulo 7, −11 is a residue modulo p if and only if p is a residue modulo 11, 13 is a residue (mod p) if and only if p is a residue modulo 13, etc. The more complicated-looking rules for the quadratic characters of 3 and −5, which depend upon congruences modulo 12 and 20 respectively, are simply the ones for −3 and 5 working with the first supplement.
Example. For −5 to be a residue (mod p), either both 5 and −1 have to be residues (mod p) or they both have to be non-residues: i.e., p ≡ ±1 (mod 5) and p ≡ 1 (mod 4) or p ≡ ±2 (mod 5) and p ≡ 3 (mod 4). Using the Chinese remainder theorem these are equivalent to p ≡ 1, 9 (mod 20) or p ≡ 3, 7 (mod 20). The generalization of the rules for −3 and 5 is Gauss's statement of quadratic reciprocity.
Statement of the theorem Quadratic Reciprocity (Gauss's statement). If q ≡ 1 ( mod 4 ) {\displaystyle q\equiv 1{\pmod {4}}} , then the congruence x 2 ≡ p ( mod q ) {\displaystyle x^{2}\equiv p{\pmod {q}}} is solvable if and only if x 2 ≡ q ( mod p ) {\displaystyle x^{2}\equiv q{\pmod {p}}} is solvable. If q ≡ 3 ( mod 4 ) {\displaystyle q\equiv 3{\pmod {4}}} and p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3{\pmod {4}}} , then the congruence x 2 ≡ p ( mod q ) {\displaystyle x^{2}\equiv p{\pmod {q}}} is solvable if and only if x 2 ≡ − q ( mod p ) {\displaystyle x^{2}\equiv -q{\pmod {p}}} is solvable. Quadratic Reciprocity (combined statement). Define q ∗ = ( − 1 ) q − 1 2 q {\displaystyle q^{*}=(-1)^{\frac {q-1}{2}}q} . Then the congruence x 2 ≡ p ( mod q ) {\displaystyle x^{2}\equiv p{\pmod {q}}} is solvable if and only if x 2 ≡ q ∗ ( mod p ) {\displaystyle x^{2}\equiv q^{*}{\pmod {p}}} is solvable. Quadratic Reciprocity (Legendre's statement). If p or q are congruent to 1 modulo 4, then: x 2 ≡ q ( mod p ) {\displaystyle x^{2}\equiv q{\pmod {p}}} is solvable if and only if x 2 ≡ p ( mod q ) {\displaystyle x^{2}\equiv p{\pmod {q}}} is solvable. If p and q are congruent to 3 modulo 4, then: x 2 ≡ q ( mod p ) {\displaystyle x^{2}\equiv q{\pmod {p}}} is solvable if and only if x 2 ≡ p ( mod q ) {\displaystyle x^{2}\equiv p{\pmod {q}}} is not solvable. The last is immediately equivalent to the modern form stated in the introduction above. It is a simple exercise to prove that Legendre's and Gauss's statements are equivalent – it requires no more than the first supplement and the facts about multiplying residues and nonresidues.
Proof
Apparently, the shortest known proof yet was published by B. Veklych in the American Mathematical Monthly.
Proofs of the supplements The value of the Legendre symbol of − 1 {\displaystyle -1} (used in the proof above) follows directly from Euler's criterion:
( − 1 p ) ≡ ( − 1 ) p − 1 2 ( mod p ) {\displaystyle \left({\frac {-1}{p}}\right)\equiv (-1)^{\frac {p-1}{2}}{\pmod {p}}}
by Euler's criterion, but both sides of this congruence are numbers of the form ± 1 {\displaystyle \pm 1} , so they must be equal. Whether 2 {\displaystyle 2} is a quadratic residue can be concluded if we know the number of solutions of the equation x 2 + y 2 = 2 {\displaystyle x^{2}+y^{2}=2} with x , y ∈ Z p , {\displaystyle x,y\in \mathbb {Z} _{p},} which can be solved by standard methods. Namely, all its solutions where x y ≠ 0 , x ≠ ± y {\displaystyle xy\neq 0,x\neq \pm y} can be grouped into octuplets of the form ( ± x , ± y ) , ( ± y , ± x ) {\displaystyle (\pm x,\pm y),(\pm y,\pm x)} , and what is left are four solutions of the form ( ± 1 , ± 1 ) {\displaystyle (\pm 1,\pm 1)} and possibly four additional solutions where x 2 = 2 , y = 0 {\displaystyle x^{2}=2,y=0} and x = 0 , y 2 = 2 {\displaystyle x=0,y^{2}=2} , which exist precisely if 2 {\displaystyle 2} is a quadratic residue. That is, 2 {\displaystyle 2} is a quadratic residue precisely if the number of solutions of this equation is divisible by 8 {\displaystyle 8} . And this equation can be solved in just the same way here as over the rational numbers: substitute x = a + 1 , y = a t + 1 {\displaystyle x=a+1,y=at+1} , where we demand that a ≠ 0 {\displaystyle a\neq 0} (leaving out the two solutions ( 1 , ± 1 ) {\displaystyle (1,\pm 1)} ), then the original equation transforms into
a = − 2 ( t + 1 ) ( t 2 + 1 ) . {\displaystyle a=-{\frac {2(t+1)}{(t^{2}+1)}}.}
Here t {\displaystyle t} can have any value that does not make the denominator zero – for which there are 1 + ( − 1 p ) {\displaystyle 1+\left({\frac {-1}{p}}\right)} possibilities (i.e. 2 {\displaystyle 2} if − 1 {\displaystyle -1} is a residue, 0 {\displaystyle 0} if not) – and also does not make a {\displaystyle a} zero, which excludes one more option, t = − 1 {\displaystyle t=-1} . Thus there are
p − ( 1 + ( − 1 p ) ) − 1 {\displaystyle p-\left(1+\left({\frac {-1}{p}}\right)\right)-1}
possibilities for t {\displaystyle t} , and so together with the two excluded solutions there are overall p − ( − 1 p ) {\displaystyle p-\left({\frac {-1}{p}}\right)} solutions of the original equation. Therefore, 2 {\displaystyle 2} is a residue modulo p {\displaystyle p} if and only if 8 {\displaystyle 8} divides p − ( − 1 ) p − 1 2 {\displaystyle p-(-1)^{\frac {p-1}{2}}} . This is a reformulation of the condition stated above.
History and alternative statements The theorem was formulated in many ways before its modern form: Euler and Legendre did not have Gauss's congruence notation, nor did Gauss have the Legendre symbol. In this article p and q always refer to distinct positive odd primes, and x and y to unspecified integers.
Fermat Fermat proved (or claimed to have proved) a number of theorems about expressing a prime by a quadratic form:
p = x 2 + y 2 ⟺ p = 2 or p ≡ 1 ( mod 4 ) p = x 2 + 2 y 2 ⟺ p = 2 or p ≡ 1 , 3 ( mod 8 ) p = x 2 + 3 y 2 ⟺ p = 3 or p ≡ 1 ( mod 3 ) {\displaystyle {\begin{aligned}p=x^{2}+y^{2}\qquad &\Longleftrightarrow \qquad p=2\quad {\text{ or }}\quad p\equiv 1{\pmod {4}}\\p=x^{2}+2y^{2}\qquad &\Longleftrightarrow \qquad p=2\quad {\text{ or }}\quad p\equiv 1,3{\pmod {8}}\\p=x^{2}+3y^{2}\qquad &\Longleftrightarrow \qquad p=3\quad {\text{ or }}\quad p\equiv 1{\pmod {3}}\\\end{aligned}}}
He did not state the law of quadratic reciprocity, although the cases −1, ±2, and ±3 are easy deductions from these and others of his theorems. He also claimed to have a proof that if the prime number p ends with 7, (in base 10) and the prime number q ends in 3, and p ≡ q ≡ 3 (mod 4), then
p q = x 2 + 5 y 2 . {\displaystyle pq=x^{2}+5y^{2}.}
Euler conjectured, and Lagrange proved, that
p ≡ 1 , 9 ( mod 20 ) ⟹ p = x 2 + 5 y 2 p , q ≡ 3 , 7 ( mod 20 ) ⟹ p q = x 2 + 5 y 2 {\displaystyle {\begin{aligned}p&\equiv 1,9{\pmod {20}}\quad \Longrightarrow \quad p=x^{2}+5y^{2}\\p,q&\equiv 3,7{\pmod {20}}\quad \Longrightarrow \quad pq=x^{2}+5y^{2}\end{aligned}}}
Proving these and other statements of Fermat was one of the things that led mathematicians to the reciprocity theorem.
Euler Translated into modern notation, Euler stated that for distinct odd primes p and q:
If q ≡ 1 (mod 4) then q is a quadratic residue (mod p) if and only if there exists some integer b such that p ≡ b2 (mod q). If q ≡ 3 (mod 4) then q is a quadratic residue (mod p) if and only if there exists some integer b which is odd and not divisible by q such that p ≡ ±b2 (mod 4q). This is equivalent to quadratic reciprocity. He could not prove it, but he did prove the second supplement.
Legendre and his symbol Fermat proved that if p is a prime number and a is an integer,
a p ≡ a ( mod p ) . {\displaystyle a^{p}\equiv a{\pmod {p}}.}
Thus if p does not divide a, using the non-obvious fact (see for example Ireland and Rosen below) that the residues modulo p form a field and therefore in particular the multiplicative group is cyclic, hence there can be at most two solutions to a quadratic equation:
a p − 1 2 ≡ ± 1 ( mod p ) . {\displaystyle a^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}.}
Legendre lets a and A represent positive primes ≡ 1 (mod 4) and b and B positive primes ≡ 3 (mod 4), and sets out a table of eight theorems that together are equivalent to quadratic reciprocity:
He says that since expressions of the form
N c − 1 2 ≡ ± 1 ( mod c ) , gcd ( N , c ) = 1 {\displaystyle N^{\frac {c-1}{2}}\equiv \pm 1{\pmod {c}},\qquad \gcd(N,c)=1}
will come up so often he will abbreviate them as:
( N c ) ≡ N c − 1 2 ( mod c ) = ± 1. {\displaystyle \left({\frac {N}{c}}\right)\equiv N^{\frac {c-1}{2}}{\pmod {c}}=\pm 1.}
This is now known as the Legendre symbol, and an equivalent definition is used today: for all integers a and all odd primes p
( a p ) = { 0 a ≡ 0 ( mod p ) 1 a ≢ 0 ( mod p ) and ∃ x : a ≡ x 2 ( mod p ) − 1 a ≢ 0 ( mod p ) and there is no such x . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}0&a\equiv 0{\pmod {p}}\\1&a\not \equiv 0{\pmod {p}}{\text{ and }}\exists x:a\equiv x^{2}{\pmod {p}}\\-1&a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{cases}}}
Legendre's version of quadratic reciprocity
( p q ) = { ( q p ) p ≡ 1 ( mod 4 ) or q ≡ 1 ( mod 4 ) − ( q p ) p ≡ 3 ( mod 4 ) and q ≡ 3 ( mod 4 ) {\displaystyle \left({\frac {p}{q}}\right)={\begin{cases}\left({\tfrac {q}{p}}\right)&p\equiv 1{\pmod {4}}\quad {\text{ or }}\quad q\equiv 1{\pmod {4}}\\-\left({\tfrac {q}{p}}\right)&p\equiv 3{\pmod {4}}\quad {\text{ and }}\quad q\equiv 3{\pmod {4}}\end{cases}}}
He notes that these can be combined:
( p q ) ( q p ) = ( − 1 ) p − 1 2 q − 1 2 . {\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}
A number of proofs, especially those based on Gauss's Lemma, explicitly calculate this formula.
The supplementary laws using Legendre symbols
( − 1 p ) = ( − 1