Law of Quadratic Reciprocity

Number Theory · Axiom Academy

LESSON The Law of Quadratic Reciprocity Understanding the beautiful symmetry between quadratic residues of different primes Before we can state the law, we need the Legendre symbol notation. For an odd prime p and integer a , the Legendre symbol is defined as: +1 if a is a quadratic residue modulo p (and a ≢ 0 mod p ) -1 if a is a quadratic non-residue modulo p In other words, (a/p) = 1 means there exists some x such that x 2 ≡ a (mod p ). 2. The Law of Quadratic Reciprocity For distinct odd primes p and q , the law states: The exponent ((p-1)/2)·((q-1)/2) determines the sign: If either p or q ≡ 1 (mod 4), the exponent is even , so (-1) raised to it equals +1 If both p and q ≡ 3 (mod 4), the exponent is odd , so (-1) raised to it equals -1 Why should such a beautiful symmetry exist? One way to understand it is through a geometric argument involving lattice points. The lattice points below the diagonal line y = (p/q)x can be counted, and this count relates directly to the Legendre symbols (p/q) and (q/p). The parity of these counts gives us the sign in the reciprocity formula. The Law of Quadratic Reciprocity allows us to efficiently compute Legendre symbols and determine whether equations have solutions. Primality testing: QR is used in some probabilistic primality tests Cryptography: Forms the basis for certain cryptographic protocols Algorithmic number theory: Enables efficient computation of square roots modulo primes

This is the written version of the interactive lesson above. See the full Number Theory course.