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:

Law of quadratic reciprocity—Let p and q be distinct odd prime numbers, and define the Legendre symbol as

Then

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 ${\displaystyle x^{2}\equiv a{\pmod {p}}}$ for an odd prime ${\displaystyle p}$; that is, to determine the "perfect squares" modulo ${\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 ${\displaystyle p\equiv 3{\pmod {4}}}$ using Euler's criterion one can give an explicit formula for the "square roots" modulo ${\displaystyle p}$ of a quadratic residue ${\displaystyle a}$, namely,

indeed,

This formula only works if it is known in advance that ${\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

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).