Quadratic Residues and Reciprocity - Examples and Constructions

The law of quadratic reciprocity provides a systematic method for computing Legendre symbols without resorting to Euler's criterion or exhaustive search. This remarkable theorem connects the solvability of two seemingly unrelated quadratic congruences.

DefinitionGauss's Lemma

Let $p$ be an odd prime and $\gcd(a, p) = 1$ . Consider the least positive residues of: $a, 2a, 3a, \ldots, \frac{p-1}{2}a \pmod{p}$

Let $n$ be the number of these residues that exceed $p/2$ . Then: $\left(\frac{a}{p}\right) = (-1)^n$

Gauss's Lemma provides an alternative computational method for the Legendre symbol and is instrumental in proving quadratic reciprocity.

ExampleGauss's Lemma Application

Compute $\left(\frac{3}{11}\right)$ using Gauss's Lemma.

Consider $3 \cdot 1, 3 \cdot 2, 3 \cdot 3, 3 \cdot 4, 3 \cdot 5$ modulo $11$ : $3, 6, 9, 12, 15 \equiv 3, 6, 9, 1, 4 \pmod{11}$

The least positive residues are $\{1, 3, 4, 6, 9\}$ . Those exceeding $11/2 = 5.5$ are $\{6, 9\}$ , so $n = 2$ .

Therefore: $\left(\frac{3}{11}\right) = (-1)^2 = 1$ .

We can verify: $5^2 = 25 \equiv 3 \pmod{11}$ .

DefinitionJacobi Symbol

Let $n = p_1^{e_1} \cdots p_k^{e_k}$ be an odd positive integer with prime factorization. For any integer $a$ , the Jacobi symbol $\left(\frac{a}{n}\right)$ is defined as: $\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \cdots \left(\frac{a}{p_k}\right)^{e_k}$

For $n = 1$ , we define $\left(\frac{a}{1}\right) = 1$ .

The Jacobi symbol generalizes the Legendre symbol to composite odd moduli. Unlike the Legendre symbol, $\left(\frac{a}{n}\right) = 1$ does not necessarily mean $a$ is a quadratic residue modulo $n$ .

ExampleJacobi Symbol

Compute $\left(\frac{2}{15}\right)$ .

Since $15 = 3 \cdot 5$ : $\left(\frac{2}{15}\right) = \left(\frac{2}{3}\right)\left(\frac{2}{5}\right)$

Using the second supplement:

$3 \equiv 3 \pmod{8}$ , so $\left(\frac{2}{3}\right) = -1$
$5 \equiv 5 \pmod{8}$ , so $\left(\frac{2}{5}\right) = -1$

Therefore: $\left(\frac{2}{15}\right) = (-1)(-1) = 1$ .

However, $2$ is not a quadratic residue modulo $15$ . The equation $x^2 \equiv 2 \pmod{15}$ has no solution because $x^2 \equiv 2 \pmod{3}$ has no solution.

Remark

The Jacobi symbol inherits the multiplicativity and reciprocity properties of the Legendre symbol: $\left(\frac{a}{m}\right)\left(\frac{a}{n}\right) = \left(\frac{a}{mn}\right)$

And the law of quadratic reciprocity extends: $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4}$ for odd positive integers $m, n$ .

ExampleUsing Quadratic Reciprocity

Determine whether $x^2 \equiv 61 \pmod{97}$ has a solution.

We need $\left(\frac{61}{97}\right)$ . By quadratic reciprocity: $\left(\frac{61}{97}\right)\left(\frac{97}{61}\right) = (-1)^{(61-1)(97-1)/4} = (-1)^{30 \cdot 48/4} = 1$

So $\left(\frac{61}{97}\right) = \left(\frac{97}{61}\right) = \left(\frac{36}{61}\right) = \left(\frac{6^2}{61}\right) = 1$ .

Therefore, $61$ is a quadratic residue modulo $97$ .

The Jacobi symbol, combined with quadratic reciprocity, provides an efficient algorithm for determining quadratic residuosity with complexity comparable to the Euclidean algorithm.