Let p and q be odd primes, with p≡q. We define the Legendre symbol (p/q) to
be 1 if p is a square modulo q and −1 otherwise. The law of quadratic reciprocity,
first proved by Gauss in 1801, states that
(p/q)(q/p) ≡ (−1)^[(p−1)(q−1)/4].