Quadratic reciprocity

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 for an odd prime ; that is, to determine the "perfect squares" modulo . 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 using Euler's criterion one can give an explicit formula for the "square roots" modulo of a quadratic residue , namely,

indeed,

This formula only works if it is known in advance that 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,Gauss, DA § 4, arts 107–150 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".E.g. in his mathematical diary entry for April 8, 1796 (the date he first proved quadratic reciprocity). See facsimile page from Felix Klein's Development of Mathematics in the 19th century He published six proofs for it, and two more were found in his posthumous papers. There are now over 240 published proofs.See F. Lemmermeyer's chronology and bibliography of proofs in the external references 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 and its values for The prime factorizations of these values are given as follows:

n         n         n 1 −4 −22 16 251 251 31 956 22⋅239 2 −1 −1 17 284 22⋅71 32 1019 1019 3 4 22 18 319 11⋅29 33 1084 22⋅271 4 11 11 19 356 22⋅89 34 1151 1151 5 20 22⋅5 20 395 5⋅79 35 1220 22⋅5⋅61 6 31 31 21 436 22⋅109 36 1291 1291 7 44 22⋅11 22 479 479 37 1364 22⋅11⋅31 8 59 59 23 524 22⋅131 38 1439 1439 9 76 22⋅19 24 571 571 39 1516 22⋅379 10 95 5⋅19 25 620 22⋅5⋅31 40 1595 5⋅11⋅29 11 116 22⋅29 26 671 11⋅61 41 1676 22⋅419 12 139 139 27 724 22⋅181 42 1759 1759 13 164 22⋅41 28 779 19⋅41 43 1844 22⋅461 14 191 191 29 836 22⋅11⋅19 44 1931 1931 15 220 22⋅5⋅11 30 895 5⋅179 45 2020 22⋅5⋅101

The prime factors dividing are , and every prime whose final digit is or ; no primes ending in or ever appear. Now, is a prime factor of some whenever , i.e. whenever i.e. whenever 5 is a quadratic residue modulo . This happens for and those primes with and the latter numbers and are precisely the quadratic residues modulo . Therefore, except for , we have that is a quadratic residue modulo iff is a quadratic residue modulo .

The law of quadratic reciprocity gives a similar characterization of prime divisors of for any prime q, which leads to a characterization for any integer .

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:

+ Squares mod primes n 12 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 n2 1 491625364964 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 mod 3 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 mod 5 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 mod 11 1 4 9 5 3 3 5 9 4 1 0 1 4 9 5 3 3 5 9 4 1 0 1 4 9 mod 13 1 4 9 3 12 10 10 12 3 9 4 1 0 1 4 9 3 12 10 10 12 3 9 4 1 mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 1 4 9 16 8 2 15 13 mod 19 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 0 1 4 9 16 6 17 mod 23 1 4 9 16 2 13 3 18 12 8 6 6 8 12 18 3 13 2 16 9 4 1 0 1 4 mod 29 1 4 9 16 25 7 20 6 23 13 5 28 24 22 22 24 28 5 13 23 6 20 7 25 16 mod 31 1 4 9 1625 5 18 2 19 7 28 20 14 10 8 8 10 14 20 28 7 19 2 18 5 mod 37 1 4 9 1625 36 12 27 7 2610 33 21 11 3 34 30 28 28 30 34 3 11 21 33 mod 41 1 4 9 1625 36 8 23 40 183921 5 32 20 10 2 37 33 31 31 33 37 2 10 mod 43 1 4 9 1625 36 6 21 38 14 35 15 40 24 10 41 31 23 17 13 11 11 13 17 23 mod 47 1 4 9 1625 36 2 17 34 6 27 3 28 8 3721742322418 14 12 12 14

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.

+ LegendR q is a residue (mod p)    q ≡ 1 (mod 4) or p ≡ 1 (mod 4)   (or both)   (reciprocating)N q is a nonresidue (mod p)   R q is a residue (mod p) q ≡ p ≡ 3 (mod 4) (non-reciprocating)N q is a nonresidue (mod p)   q 3 5 7111317192329313741434753596167717379838997 p 3  N R N RN RNN RR NRN NN R R N R R N NR 5N   N R N N R NRRN RN N N R R N R N R N R N 7N N   R N N N R R N R N R N R N N R RN R N N N 11R R N   N N N R N R R N N R R R N R R N N N R R 13R N N N   R N R R N N N R N R N R N N N R N N N 17N N N N R  R N N N N N R R R R N R N N N R R N 19N R R R N R   R N N N N R R N N R N N R N R N N 23R N N N R N N   R R N R N R N R N N R R N N N N 29N R R N R N N R   N N N N N R R N R R N N R N N 31N R R N N N R N N   N R N R N R N R R N N N N R 37R N R R N N N N N N   R N R R N N R R R N R N N 41N R N N N N N R N R R   R N N R R N N R N R N N 43N N N R R R N R N R N R   R R R N R N N R R N R 47R N R N N R N N N N R N N   R R R N R N R R R R 53N N R R R R N N R N R N R R   R N N N N N N R R 59R R R N N R R N R N N R N N R   N N R N R N N N 61R R N N R N R N N N N R N R N N   N N R N R N R 67N N N N N R R R R N R N N R N R N   R R N R R N 71R R N N N N R N R N R N R N N N N N   R R R R N 73R N N N N N R R N N R R N N N N R R R   R N R R 79N R N R R N R R N R N N N N N N N R N R   R R R 83R N R R N R N R R R R R N N N R R N N N N   N N 89N R N R N R N N N N N N N R R N N R R R R N   R 97R N N R N N N N N R N N R R R N R N N R R N R  

Ordering the rows and columns mod 4 makes the pattern clearer.

q8379716759474331231911 7 3 513172937415361738997 p83  N N N R N N R R N R R R N N R R R R N R N N N 79R   N R N N N R R R R N N R R N N N N N N R R R 71R R   N N N R N N R N N R R N N R R N N N R R N 67R N R   R R N N R R N N N N N R R R N N N R R N 59N R R N   N N N N R N R R R N R R N R R N N N N 47R R R N R   N N N N N R R N N R N R N R R N R R 43R R N R R R   R R N R N N N R R N N R R N N N R 31N N R R R R N   N R N R N R N N N N R N N N N R 23N N R N R R N R   N N N R N R N R N R N N R N N 19R N N N N R R N R   R R N R N R N N N N R R N N 11N N R R R R N R R N   N R R N N N R N R N N R R 7N R RR N N R N R N R   N N N N R R N R N N N N 3N R N R N N RRNRN R   N RN N R NNR R NR 5N R R N R N N RNR R N N   N N RN RN R N R N 13N R N N N N R N R N N N R N   R R N N R R N N N 17R N N R R R R N N R N N N N R  N N N R N N R N 29R N R R R N N N R N N R N R R N   N N R N N N N 37R N R R N R N N N N R R R N N N N   R R N R N N 41R N N N R N R R R N N N N R N N N R   N R R N N 53N N N N R R R N N N R R N N R R R R N   N N R R 61R N N N N R N N N R N N R R R N N N R N   R N R 73N R R R N N N N R R N N R N N N N R R N R   R R 89N R R R N R N N N N R N N R N R N N N R N R   R 97N R N N N R R R N N R N R N N N N N N R R R R  

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 is solvable if and only if 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 is solvable if and only if 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