Quadratic Residues, Legendre Symbols, and Gauss's Lemma

This lecture introduces quadratic residues modulo primes, the Legendre symbol as a tool for determining when a number is a square, and Gauss's Lemma as a method for computing the Legendre symbol.

Quadratic Residues

Definition (Quadratic Residue)

Let $n$ be a positive integer and $a$ be an integer. We say that $a$ is a quadratic residue modulo $n$ if there exists an integer $x$ such that $$x^2 \equiv a \pmod{n}.$$ If no such $x$ exists, then $a$ is called a quadratic non-residue modulo $n$.

In other words, $a$ is a quadratic residue modulo $n$ if $a$ is a "square" modulo $n$.

Examples:

Modulo 7: The squares modulo 7 are:

- $1^2 \equiv 1 \pmod{7}$ - $2^2 \equiv 4 \pmod{7}$ - $3^2 \equiv 9 \equiv 2 \pmod{7}$ - $4^2 \equiv 16 \equiv 2 \pmod{7}$ - $5^2 \equiv 25 \equiv 4 \pmod{7}$ - $6^2 \equiv 36 \equiv 1 \pmod{7}$

So the quadratic residues modulo 7 are $\{1, 2, 4\}$, and the non-residues are $\{3, 5, 6\}$.

Modulo 11: We have $1^2 = 1$, $2^2 = 4$, $3^2 = 9$, $4^2 = 5$, $5^2 = 3$ (all mod 11). So the quadratic residues modulo 11 are $\{1, 3, 4, 5, 9\}$.

Let's verify these computationally:

Here's a function to compute all quadratic residues modulo any integer $n$:

The Legendre Symbol

To work efficiently with quadratic residues modulo a prime $p$, we introduce the Legendre symbol.

Definition (Legendre Symbol)

Let $p$ be an odd prime and $a$ be an integer. The Legendre symbol $\left( \frac{a}{p} \right)$ is defined as: $$\left( \frac{a}{p} \right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0 \pmod{p}, \\ -1 & \text{if } a \text{ is a quadratic non-residue modulo } p, \\ 0 & \text{if } a \equiv 0 \pmod{p}. \end{cases}$$

Important Note: The Legendre symbol $\left( \frac{a}{p} \right)$ looks like a fraction, but it is not a fraction! It's simply notation for indicating whether $a$ is a square modulo $p$.

Examples:

$\left( \frac{1}{7} \right) = 1$ because $1 \equiv 1^2 \pmod{7}$
$\left( \frac{2}{7} \right) = 1$ because $2 \equiv 3^2 \pmod{7}$
$\left( \frac{3}{7} \right) = -1$ because $3$ is not a quadratic residue modulo $7$
$\left( \frac{4}{7} \right) = 1$ because $4 \equiv 2^2 \pmod{7}$

Properties of the Legendre Symbol

The Legendre symbol has several important properties that make it useful for computations:

Theorem (Multiplicativity)

Let $p$ be an odd prime and $a, b$ be integers. Then $$\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right).$$

This means that the Legendre symbol is multiplicative. For example:

$\left( \frac{6}{7} \right) = \left( \frac{2 \cdot 3}{7} \right) = \left( \frac{2}{7} \right) \left( \frac{3}{7} \right) = (1)(-1) = -1$

Let's compute some Legendre symbols:

Euler's Criterion

While the definition of the Legendre symbol is straightforward, checking all squares to determine if $a$ is a quadratic residue is inefficient. Euler's Criterion provides a much faster method.

Theorem (Euler's Criterion)

Let $p$ be an odd prime and $a$ be an integer with $\gcd(a, p) = 1$. Then $$\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}.$$

This gives us a computational method: to determine if $a$ is a quadratic residue modulo $p$, simply compute $a^{(p-1)/2} \bmod p$:

If the result is $1$, then $a$ is a quadratic residue
If the result is $-1 \equiv p-1 \pmod{p}$, then $a$ is a non-residue

Why does this work? By Fermat's Little Theorem, $a^{p-1} \equiv 1 \pmod{p}$, so $a^{(p-1)/2}$ is a square root of $1$ modulo $p$. The only square roots of $1$ modulo $p$ are $\pm 1$.

Let's verify Euler's Criterion:

Gauss's Lemma

Gauss's Lemma provides another method for computing the Legendre symbol that's based on counting negative residues in a specific set.

The Set $S(a,p)$

Definition

Let $p$ be an odd prime and $a$ be an integer with $\gcd(a, p) = 1$. Define $$S(a, p) = \left\{a \bmod_{\pm} p, \, 2a \bmod_{\pm} p, \, 3a \bmod_{\pm} p, \, \ldots, \, \frac{p-1}{2}a \bmod_{\pm} p\right\}$$ where $x \bmod_{\pm} p$ denotes the unique integer in the range $\left[-\frac{p}{2}, \frac{p}{2}\right]$ that is congruent to $x$ modulo $p$.

In other words, we take the multiples $a, 2a, 3a, \ldots, \frac{p-1}{2}a$ and reduce them modulo $p$ to lie in the symmetric interval around zero.

Example: Let $p = 7$ and $a = 3$. Then:

$1 \cdot 3 = 3 \equiv 3 \pmod{7}$ → in range $[-3, 3]$: $3$
$2 \cdot 3 = 6 \equiv 6 \equiv -1 \pmod{7}$ → in range $[-3, 3]$: $-1$
$3 \cdot 3 = 9 \equiv 2 \pmod{7}$ → in range $[-3, 3]$: $2$

So $S(3, 7) = \{3, -1, 2\}$.

Let's write code to compute $S(a, p)$:

Exploration: Investigate $S(a,p)$

Exploratory Problem: Investigate the structure of $S(a,p)$ for various values of $a$ and $p$.

What patterns do you notice?
How does the number of negative elements $\mu(a,p)$ relate to whether $a$ is a quadratic residue?
Try computing $S(a,p)$ for several different primes and values of $a$.

Use the cell below to explore:

Statement of Gauss's Lemma

The pattern you may have noticed in the exploration above is formalized by Gauss's Lemma:

Theorem (Gauss's Lemma)

Let $p$ be an odd prime and $a$ be an integer with $\gcd(a, p) = 1$. Let $\mu(a, p)$ be the number of negative elements in $S(a, p)$. Then $$\left( \frac{a}{p} \right) = (-1)^{\mu(a,p)}.$$

In other words:

If $\mu(a,p)$ is even, then $\left( \frac{a}{p} \right) = 1$ (so $a$ is a quadratic residue)
If $\mu(a,p)$ is odd, then $\left( \frac{a}{p} \right) = -1$ (so $a$ is a non-residue)

Example: We computed $S(3, 7) = \{3, -1, 2\}$, which has $\mu(3, 7) = 1$ negative element. Thus: $$\left( \frac{3}{7} \right) = (-1)^1 = -1$$ So $3$ is a quadratic non-residue modulo $7$.

Let's verify Gauss's Lemma for several values: