Quadratic reciprocity and its applications

For distinct odd primes p and q, multiply the two Legendre symbols obtained by exchanging numerator and denominator. Reciprocity says that this product is negative one precisely when p and q are both three modulo four, and positive one otherwise. Since neither symbol is zero in the distinct-prime case, this determines either symbol from the other. If the primes are equal, both original symbols are zero and this formula does not apply.

The theorem is much deeper than the arithmetic rules that implement it. One way to understand the source of the sign uses Gauss’s lemma: multiply the lower-half residues by a numerator and count how often their least positive representatives fall in the upper half. That count determines the Legendre symbol’s sign. Comparing the two counts for p and q yields a lattice-point parity relation. We use reciprocity as a proved theorem here, rather than pretending a few examples establish it.

The numerator negative one is a square exactly when p is one modulo four. This follows directly from Euler’s criterion. The numerator two has symbol one when p is one or seven modulo eight and negative one when p is three or five modulo eight. These are supplementary laws, not cases obtained by treating two or negative one as odd primes in reciprocity. Their separate hypotheses keep a symbol calculation well defined.

To evaluate a general numerator, first reduce it modulo the prime denominator, then factor it into a sign, powers of two, and odd prime factors. Use multiplicativity to separate the factors. Every even exponent contributes one provided the prime denominator does not divide that factor. A zero factor gives symbol zero immediately. Apply reciprocity only to the remaining odd prime factors, and reduce the new numerators after each swap.

Write every swap with its sign before simplifying residues. This prevents a common error: reducing the new numerator correctly but losing the minus sign when both primes are three modulo four. The denominator usually becomes smaller after a swap and reduction, giving an efficient descent toward a small symbol. For a composite numerator, factorization or the more general Jacobi-symbol algorithm can organize the work, but the Legendre definition still requires a prime denominator.

A final symbol of negative one proves that a square congruence has no solution. A symbol of one proves existence, not the roots themselves, and it is not a primality certificate for the denominator. In an equation over integers, finding a modular obstruction can disprove integer solvability, while absence of one chosen obstruction cannot prove solvability. Distinguishing these logical directions makes reciprocity useful in Diophantine reasoning without asking the theorem to establish more than it says.