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
- x2 = p (mod q)
has a solution
x if and only if the congruence
- x2 = 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
- x2 = p (mod q)
has a solution
x if and only if the congruence
- x2 = 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: