Quadratic Reciprocity

Quadratic Reciprocity

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers. There are a number of equivalent statements of the theorem, which consists of two "supplements" and the reciprocity law:

Let p, q > 2 be two distinct prime numbers. Then

(Supplement 1)

x2 ≡ −1 (mod p) is solvable if and only if p ≡ 1 (mod 4).

(Supplement 2)

x2 ≡ 2 (mod p) is solvable if and only if p ≡ ±1 (mod 8).

(Quadratic reciprocity)
Let q* = ±q where the sign is plus if q ≡ 1 (mod 4) and minus if q ≡ −1 (mod 4). (I.e. |q*| = q and q* ≡ 1 (mod 4).) Then

x2 ≡ p (mod q) is solvable if and only if x2 ≡ q* (mod p) is solvable.

Although the law can be used to tell whether any quadratic equation modulo a prime number has a solution, it does not provide any help at all for actually finding the solution. (The article on quadratic residues discusses algorithms for this.)

The theorem was conjectured by Euler and Legendre and first proven by Gauss. He refers to it as the "fundamental theorem" in the Disquisitiones Arithmeticae and his papers; privately he referred to it as the "golden theorem." He published six proofs, and two more were found in his posthumous papers. There are now over 200 published proofs.

The first section of this article does not use the Legendre symbol and gives the formulations of quadratic reciprocity found by Legendre and Gauss. The Legendre-Jacobi symbol is introduced in the second section.

Read more about Quadratic Reciprocity:  Terminology, Data, and Two Statements of The Theorem, History and Alternative Statements, Higher Powers

Famous quotes containing the word reciprocity:

    Between women love is contemplative; caresses are intended less to gain possession of the other than gradually to re-create the self through her; separateness is abolished, there is no struggle, no victory, no defeat; in exact reciprocity each is at once subject and object, sovereign and slave; duality become mutuality.
    Simone De Beauvoir (1908–1986)