This site is supported by donations to The OEIS Foundation.

Please do not rely on any information it contains.

The quadratic reciprocity law concerns congruences modulo odd primes. The solubility of ${\displaystyle x^{2}\equiv p{\pmod {q}}}$ and ${\displaystyle x^{2}\equiv q{\pmod {p}}}$ depends on whether both of the primes are congruent to 3 modulo 4.

Theorem. Given distinct odd primes ${\displaystyle p}$ and ${\displaystyle q}$,

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}},}$

where ${\displaystyle \left({\frac {a}{p}}\right)}$ is the Legendre symbol.

Proof. A PROOF GOES HERE. (END OF PROOF MARK)

For example, both 13 and 17 are congruent to 1 modulo 4. We see that ${\displaystyle 8^{2}\equiv 13{\pmod {17}}}$ and ${\displaystyle 11^{2}\equiv 17{\pmod {13}}}$. These two primes "reciprocate" each other as quadratic residues.

Compare 11 and 19. The quadratic reciprocity law tells us one is quadratic residue of the other but not vice-versa. Indeed ${\displaystyle 7^{2}\equiv 11{\pmod {19}}}$, but ${\displaystyle x^{2}\equiv 19{\pmod {11}}}$ has no solutions. These two primes do not "reciprocate."

Gauss's first proof of April 8, 1796 is now considered inelegant by some. Soon after that same year, on June 27, Gauss came up with a proof using quadratic forms.