Mathematics
Quadratic Reciprocity: The Law of Modular Arithmetic
Quick fact
For any two odd primes p and q, the question of whether p is a square modulo q is answered by the sign of (-1)^((p-1)(q-1)/4), a single bit of information that depends only on the primes themselves.
Why this is interesting
You know that 1 is a perfect square, and that 4 is a perfect square. But what does it mean to be a square in the world of remainders? The answer holds a hidden symmetry that has fascinated mathematicians for centuries.
Read the full explanation
Understanding Quadratic Reciprocity: The Law of Modular Arithmetic
Start with a familiar idea: on a clock, numbers wrap around after 12. Modular arithmetic is like that, but with a fixed number called the modulus. Now, imagine asking whether a number is a perfect square in this wrapped world. For example, modulo 7, the squares are 1, 2, and 4 (since 1^2=1, 2^2=4, 3^2=2, and so on). These are called quadratic residues. The question at the heart of quadratic reciprocity is: given two primes p and q, can we tell whether p is a quadratic residue modulo q? The surprise is that the answer is not random – it reveals a deep symmetry. If p is a square modulo q, then in most cases q is also a square modulo p, with a simple adjustment when both primes are 3 modulo 4. This reciprocity is the law.
A deeper explanation
The law of quadratic reciprocity, proven by Gauss, provides an efficient way to compute whether a number is a quadratic residue modulo a prime. It uses the Legendre symbol (a/p), which is 1 if a is a square modulo p and -1 otherwise. The law states that for odd primes p and q, (p/q)(q/p) = (-1)^((p-1)(q-1)/4). This compact formula resolves the question by reducing it to checking the residues of the primes modulo 4. The mechanism behind this lies in the structure of the multiplicative group modulo a prime and can be proven using Gauss's lemma or the properties of sums of powers. This law matters because it turns a potentially time-consuming search for square roots into a quick symbolic calculation, making it a cornerstone of number theory and a tool in modern algorithms like primality testing and cryptography.