Quadratic Residues & Reciprocity

Discover which numbers are perfect squares modulo a prime, and Gauss's "Golden Theorem"

Gauss's Golden Theorem

Which numbers are perfect squares modulo a prime? The answer reveals deep structure: exactly half of the nonzero residues are quadratic residues (QRs), and the Legendre symbol (a/p) encodes this information elegantly.

Quadratic reciprocity, which Gauss called the theorema aureum(golden theorem), relates the solvability of x² ≡ p (mod q) to that of x² ≡ q (mod p). It is one of the most beautiful results in all of mathematics, connecting to Galois Theory through cyclotomic fields and Artin reciprocity.

Demo 1: Quadratic Residue Grid

For a prime p, square each element 1, 2, ..., p-1 modulo p. The values that appear are the quadratic residues; those that don't are the non-residues. Notice: there are always exactly (p-1)/2 quadratic residues.

6 QRs, 6 NRs
1
↓ ²
1
2
↓ ²
4
3
↓ ²
9
4
↓ ²
3
5
↓ ²
12
6
↓ ²
10
7
↓ ²
10
8
↓ ²
12
9
↓ ²
3
10
↓ ²
9
11
↓ ²
4
12
↓ ²
1
Quadratic Residues (6)
13491012
Non-Residues (6)
2567811

Exactly (p-1)/2 = 6 elements are quadratic residues mod p.

Demo 2: Legendre Symbol Calculator

The Legendre symbol (a/p) equals +1 if a is a QR, -1 if a is an NR, and 0 if p divides a. Euler's criterion computes it efficiently: (a/p) = a(p-1)/2 mod p. This connects directly back to Fermat's Little Theorem.

(5/13) = -1
Input:a = 5, p = 13
Reduce a mod p:5 mod 13 = 5
Euler's criterion exponent:(p-1)/2 = 6
Compute:5^6 mod 13 = 12
Interpret:12 ≡ -1 → NR (Legendre symbol = -1)
All Legendre symbols mod 13:
1
2
3
4
5
6
7
8
9
10
11
12

Demo 3: Quadratic Reciprocity

For odd primes p and q: (p/q)(q/p) = (-1)((p-1)/2)((q-1)/2). The Eisenstein proof counts lattice points in a rectangle split by a diagonal — the points below (amber) and above (blue) determine the Legendre symbols.

(5/11)
1
(11/5)
1
Product
1
(-1)^10
1
x (1 to (p-1)/2 = 2)y

Below diagonal: 6 points, Above: 4 points, Total: 10

Quadratic Reciprocity: (5/11)(11/5) = (-1)^((5-1)/2 · (11-1)/2) = (-1)^10 = 1

Demo 4: Gaussian Integers

The ring Z[i] of Gaussian integers (a + bi with a, b integers) extends number theory to the complex plane. Which Gaussian integers are prime? The answer depends on ordinary primes: p = 2 and primes p ≡ 1 (mod 4) split in Z[i], while primes p ≡ 3 (mod 4) remain prime. This connects to Galois Theory via the number field Q(i).

ReIm

A prime p is a sum of two squares iff p = 2 or p ≡ 1 (mod 4). Such primes split in Z[i]; primes ≡ 3 (mod 4) remain prime.

Reciprocity Revealed!

You've explored the algebraic heart of number theory:

  • Quadratic residues and their symmetric distribution mod p
  • The Legendre symbol and Euler's criterion
  • Gauss's Golden Theorem via lattice-point counting
  • Gaussian integers and the splitting of primes in Z[i]

Next: We explore continued fractions — the most natural way to approximate real numbers — and use them to solve Pell's equation.