Quadratic reciprocity

The law of quadratic reciprocity, conjectured by Euler and Legendre and first satisfactorily proved by Gauss, connects the solvability of two related quadratic equations in modular arithmetic. As a consequence, it allows to determine the solvability of any quadratic equation in modular arithmetic.

Suppose p and q are two different odd primes. If at least one of them is congruent to 1 modulo 4, then the congruence

x² = p (mod q)

has a solution x if and only if the congruence

x² = q (mod p)

has a solution x. (The two solutions will in general be different.) On the other hand, if both primes are congruent to 3 modulo 4, then the congruence

x² = p (mod q)

has a solution x if and only if the congruence

x² = q (mod p)

does not have a solution x.

Using the Legendre symbol, these statements may be summarized as

(p/q)·(q/p) = (-1)^{(p-1)/2·(q-1)/2}

---

External links:

• A "play" comparing two proofs of the quadratic reciprocity law