Quadratic Reciprocity

The Law of Quadratic Reciprocity is the "Golden Theorem" of number theory. It relates the solvability of $x^{2} \equiv p (mod q)$ to $x^{2} \equiv q (mod p)$ .

Statement

Theorem (Law of Quadratic Reciprocity)

Let

p

and

q

be distinct odd primes. Then:

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}

Interpretation

The product is

(- 1)^{something}

If at least one prime is of the form $4 k + 1$ , the exponent is even, so the product is 1.

$(\frac{p}{q}) = (\frac{q}{p})$ ("Reciprocity holds").
If both primes are of the form $4 k + 3$ , the exponent is odd, so the product is -1.

$(\frac{p}{q}) = - (\frac{q}{p})$ ("Reciprocity flips").

Algorithm for Legendre Symbols

To evaluate

(\frac{a}{p})

Extract square factors: $(\frac{a}{p}) = (\frac{b}{p})$ where $a = k^{2} b$ .
Invert: Use Reciprocity to flip $(\frac{q}{p})$ to $\pm (\frac{p}{q})$ (reducing the modulus).
Reduce: $p (mod q)$ .
Repeat.

Practice Problems

Exercise (Problem 1)

Compute

(\frac{30}{101})

Exercise (Problem 2)

Determine if 3 is a quadratic residue modulo 31.

Exercise (Problem 3)

Prove that there are infinitely many primes of the form

10 k - 1