In mathematics, in number theory, the law of quadratic reciprocity connects the solvability of two related quadratic equations in modular arithmetic. As a consequence, it allows us to determine the solvability of any quadratic equation in modular arithmetic, even though it does not provide an efficient method for actually finding a solution.

It was conjectured by Euler and Legendre and first satisfactorily proven by Gauss. Gauss called it the 'golden theorem' and was so fond of it that he went on to provide more than seven separate proofs over his lifetime.

Franz Lemmermeyer's book Reciprocity Laws: From Euler to Eisenstein, published in 2000, collects literature citations for 196 different published proofs for the quadratic reciprocity law.

Suppose that p and q are two different prime numbers, neither of which is 2. The theorem relates the solvability of the equation

to the solvability of the equation

(see modular arithmetic). There are two cases, depending on whether p and q are congruent to 1 or to 3 (mod 4).

In this case, the theorem says that (A) has a solution if and only if (B) has a solution. That is, either they both have solutions, or they both do not.

For example, if p = 13 and q = 17 (both of which are congruent to 1 mod 4), then (A) has the solution

and (B) has a solution

On the other hand, if p = 5 and q = 13, then neither (A) nor (B) has a solution (this can be checked by simply listing all of the squares modulo 5 and modulo 13).

The theorem says nothing about the actual solutions themselves, only about whether or not they exist.

In this case, the theorem says that (A) has a solution if and only if (B) does not have a solution.

For example, if p = 7 and q = 19, then (A) has the solution

but (B) does not have a solution.

There are two extra statements which round out the above laws. Suppose again that p is a prime, not equal to 2. The first says that the equation

has a solution if p is congruent to 1 mod 4, but does not have a solution if it is congruent to 3 mod 4. For example, if p = 29, there is a solution

but for p = 7 there is no solution.

The second says that the equation

has a solution if and only if p is congruent to 1 or 7 modulo 8, but not if it is congruent to 3 or 5 modulo 8.

The theorem can be stated more compactly using the Legendre symbol:

The theorem states that if p and q are two different odd primes, then, using Gauss's original formulation:

if p is of the form 4k + 1

if p is of the form 4k + 3

Which is also equivalent to the very similar form, commonly used today:

if one or both of p and q are of the form 4k + 1

if both p and q are of the form 4k + 3

Since is odd if and only if both primes are of the form 4k + 3, we have another commonly-used form:

This last form also holds for the Jacobi symbol as well as the Legendre symbol, so that the following is true for non-prime m and n as long as both are relatively prime to each other:

The supplementary theorems then state that for any odd prime p,

and

There are cubic, quartic (biquadratic) and other higher reciprocity laws; but since two of the cube roots of 1 (root of unity) are not real, cubic reciprocity is outside the arithmetic of the rational numbers (and the same applies to higher laws).

• Fermat's theorem on sums of two squares

• Proofs of quadratic reciprocity
• Gauss lemma
• Jacobi symbol

• Quadratic Reciprocity Theorem from MathWorld
• A play comparing two proofs of the quadratic reciprocity law