Quadratic Reciprocity Theorem

Also called the Aureum Theorema (Golden Theorem) by Gauß. If $p$ and $q$ are distinct Odd Primes, then the Congruences

$x^2\equiv q\ \left({{\rm mod\ } {p}}\right)$
$x^2\equiv p\ \left({{\rm mod\ } {q}}\right)$

are both solvable or both unsolvable unless both $p$ and $q$ leave the remainder 3 when divided by 4 (in which case one of the Congruences is solvable and the other is not). Written symbolically,

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

where

$$\left({p\over q}\right)\equiv \cases{ 1 & for $x^2\equiv p\ ... ...v p\ \left({{\rm mod\ } {q}}\right)$\ not solvable for $x$\cr}$$

is known as a Legendre Symbol. Legendre was the first to publish a proof, but it was fallacious. Gauß was the first to publish a correct proof. The quadratic reciprocity theorem was Gauss's favorite theorem from Number Theory, and he devised many proofs of it over his lifetime.

See also Jacobi Symbol, Kronecker Symbol, Legendre Symbol, Quadratic Residue, Reciprocity Theorem

References

Courant, R. and Robbins, H. What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, p. 39, 1996.

Ireland, K. and Rosen, M. ``Quadratic Reciprocity.'' Ch. 5 in A Classical Introduction to Modern Number Theory, 2nd ed. New York: Springer-Verlag, pp. 50-65, 1990.

Nagell, T. ``Theory of Quadratic Residues.'' Ch. 4 in Introduction to Number Theory. New York: Wiley, 1951.

Riesel, H. ``The Law of Quadratic Reciprocity.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 279-281, 1994.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 42-49, 1993.