Quadratic Residues and the Legendre Symbol

Understanding when a quadratic congruence has a solution is a fundamental problem in number theory with deep implications for algorithms and cryptography. This topic provides the tools to answer questions like: "For a given prime $p$, which integers $a$ are perfect squares modulo $p$?" The answer lies in the elegant theory of quadratic residues, quantified by the Legendre symbol, and governed by the powerful Law of Quadratic Reciprocity.

Defining Quadratic Residues and Nonresidues

Let $p$ be an odd prime and let $a$ be an integer such that $p\nmid a$ (i.e., $a$ is not divisible by $p$). We say $a$ is a quadratic residue modulo $p$ if the congruence $x^2\equiv a(\mathrm{mod}p)$ has a solution. If the congruence has no solution, then $a$ is a quadratic nonresidue modulo $p$.

For example, consider the prime $p=7$. The squares modulo $7$ are: $$1^2\equiv 1,2^2\equiv 4,3^2\equiv 2,4^2\equiv 2,5^2\equiv 4,6^2\equiv 1(\mathrm{mod}7).$$ Thus, the quadratic residues modulo $7$ are $1$, $2$, and $4$. The numbers $3$, $5$, and $6$ are quadratic nonresidues. A key observation is that exactly half of the non-zero integers modulo an odd prime are quadratic residues. In general, for an odd prime $p$, there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ quadratic nonresidues.

The Legendre Symbol and Euler's Criterion

To efficiently encode this information, Adrien-Marie Legendre introduced a notation now called the Legendre symbol. For an odd prime $p$ and integer $a$, it is defined as: $$\left(\frac{a}{p}\right)=\{\begin{array}{ll}1& \text{if }a\text{ is a quadratic residue modulo }p\text{ and }p\nmid a,\\ -1& \text{if }a\text{ is a quadratic nonresidue modulo }p,\\ 0& \text{if }p\mid a.\end{array}$$

The Legendre symbol is a compact way to ask and answer the question of solvability. Computing it directly from the definition requires checking half the numbers modulo $p$, which is inefficient. Fortunately, Euler's criterion provides a direct computational formula: $$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p).$$ The result is either $1$ or $-1$ modulo $p$ (or $0$ if $p\mid a$). For instance, to compute $\left(\frac{3}{11}\right)$, we calculate $3^{(11-1)/2}=3^5=243\equiv 1(\mathrm{mod}11)$. Therefore, $\left(\frac{3}{11}\right)=1$, confirming $3$ is a quadratic residue modulo $11$ (indeed, $5^2\equiv 3(\mathrm{mod}11)$).

Euler's criterion also leads to two immediate multiplicative properties of the Legendre symbol:

1. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.
2. $\left(\frac{a^2}{p}\right)=1$, provided $p\nmid a$.

These properties allow you to break down the computation of a Legendre symbol into its prime factors.

The Law of Quadratic Reciprocity

While Euler's criterion is conceptually powerful, performing modular exponentiation with large numbers is computationally heavy. The Law of Quadratic Reciprocity, first proven fully by Carl Friedrich Gauss, provides a dramatically more efficient method for calculation. This law establishes a profound relationship between the quadratic characters of two different odd primes.

Theorem (Quadratic Reciprocity): Let $p$ and $q$ be distinct odd primes. Then: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$$ This is often stated in two equivalent, more actionable forms:

• If either $p\equiv 1(\mathrm{mod}4)$ or $q\equiv 1(\mathrm{mod}4)$, then $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$.
• If both $p\equiv 3(\mathrm{mod}4)$ and $q\equiv 3(\mathrm{mod}4)$, then $\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)$.

To use reciprocity effectively, you combine it with two supplementary rules:

1. The First Supplementary Law: $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}$. This equals $1$ if $p\equiv 1(\mathrm{mod}4)$ and $-1$ if $p\equiv 3(\mathrm{mod}4)$.
2. The Second Supplementary Law: $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}$. This equals $1$ if $p\equiv \pm 1(\mathrm{mod}8)$ and $-1$ if $p\equiv \pm 3(\mathrm{mod}8)$.

Consider computing $\left(\frac{42}{61}\right)$. First, factor: $\left(\frac{2\cdot 3\cdot 7}{61}\right)=\left(\frac{2}{61}\right)\left(\frac{3}{61}\right)\left(\frac{7}{61}\right)$.

• For $\left(\frac{2}{61}\right)$: Since $61\equiv 5(\mathrm{mod}8)$, the second supplementary law gives $1$.
• For $\left(\frac{3}{61}\right)$: Reciprocity applies. Since $3\equiv 3(\mathrm{mod}4)$ and $61\equiv 1(\mathrm{mod}4)$, we have $\left(\frac{3}{61}\right)=\left(\frac{61}{3}\right)=\left(\frac{1}{3}\right)=1$.
• For $\left(\frac{7}{61}\right)$: Both $7$ and $61$ are $\equiv 1(\mathrm{mod}4)$, so $\left(\frac{7}{61}\right)=\left(\frac{61}{7}\right)=\left(\frac{5}{7}\right)$.
• Now compute $\left(\frac{5}{7}\right)$. Since $5\equiv 1(\mathrm{mod}4)$, reciprocity gives $\left(\frac{5}{7}\right)=\left(\frac{7}{5}\right)=\left(\frac{2}{5}\right)$. By the second supplementary law, $5\equiv 5(\mathrm{mod}8)$, so $\left(\frac{2}{5}\right)=-1$.

Multiplying the results: $1\cdot 1\cdot (-1)=-1$. Thus, $42$ is a quadratic nonresidue modulo $61$.

The Jacobi Symbol for Efficient Computation

When the denominator in a Legendre symbol calculation is not prime, you cannot directly apply reciprocity. However, for odd composite integers, we use the Jacobi symbol, a generalization denoted $\left(\frac{a}{n}\right)$ for an odd integer $n>1$ with prime factorization $n=p_1^{e_1}{p}_2^{e_2}...p_k^{e_k}$. It is defined in terms of the Legendre symbol: $$\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{e_1}{\left(\frac{a}{p_2}\right)}^{e_2}\cdots {\left(\frac{a}{p_k}\right)}^{e_k}.$$

Crucially, the Jacobi symbol retains the same multiplicative properties and obeys the same reciprocity laws as the Legendre symbol. However, its meaning is different: a Jacobi symbol of $1$ does not guarantee that $a$ is a quadratic residue modulo $n$. Its primary utility is computational. It allows you to apply the reciprocity algorithm without needing to factor the denominator, which is a massive advantage. This efficiency is exploited in algorithms like the Solovay-Strassen primality test.

For example, to compute the Jacobi symbol $\left(\frac{21}{55}\right)$ where $55=5\cdot 11$: $$\left(\frac{21}{55}\right)=\left(\frac{21}{5}\right)\left(\frac{21}{11}\right)=\left(\frac{1}{5}\right)\left(\frac{-1}{11}\right)=1\cdot (-1)=-1.$$ Here, $-1$ as a Jacobi symbol tells us that $21$ is not a quadratic residue modulo at least one of the prime factors of $55$ (in fact, it's a nonresidue modulo both $5$ and $11$).

Applications to Representing Primes by Quadratic Forms

A classic application of this theory is determining which primes can be represented by certain binary quadratic forms. For instance, consider the question: "Which odd primes $p$ can be written as $p=x^2+y^2$ for integers $x$ and $y$?"

The answer is deeply connected to quadratic residues modulo $p$. A prime $p>2$ can be expressed as a sum of two squares if and only if $p\equiv 1(\mathrm{mod}4)$. The reasoning uses the fact that $p=x^2+y^2$ implies $x^2\equiv -y^2(\mathrm{mod}p)$, or $(x{y}^{-1}{)}^2\equiv -1(\mathrm{mod}p)$. Therefore, $-1$ must be a quadratic residue modulo $p$. By the first supplementary law, this happens exactly when $p\equiv 1(\mathrm{mod}4)$.

Similarly, determining which primes are of the form $p=x^2+2y^2$ involves checking whether $-2$ is a quadratic residue modulo $p$. Using the properties of the Legendre symbol, $\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)$. Analyzing the conditions for this product to equal $1$ leads to the conclusion that $p=x^2+2y^2$ is possible precisely when $p\equiv 1$ or $3(\mathrm{mod}8)$. These results are prototypical examples of the deep interplay between quadratic reciprocity and the theory of quadratic forms.

Common Pitfalls

1. Assuming the Jacobi symbol implies a quadratic residue. The most frequent error is interpreting a Jacobi symbol $\left(\frac{a}{n}\right)=1$ as proof that $x^2\equiv a(\mathrm{mod}n)$ is solvable. Remember, the Jacobi symbol is a computational tool that generalizes the Legendre symbol's notation and rules, but its output of $1$ only guarantees that $a$ is a quadratic residue modulo $n$ if $n$ is prime. For composite $n$, it is a necessary but not sufficient condition.
2. Misapplying Quadratic Reciprocity. Reciprocity only applies to odd primes. A common mistake is to try to use it on a symbol like $\left(\frac{4}{p}\right)$, where the numerator is composite. You must first factor the numerator using the multiplicative property: $\left(\frac{4}{p}\right)={\left(\frac{2}{p}\right)}^2=1$, making reciprocity unnecessary.
3. Forgetting to "reduce the numerator modulo the denominator." Before applying any law, you should always reduce $a$ modulo $p$ when computing $\left(\frac{a}{p}\right)$. For example, $\left(\frac{15}{7}\right)$ should first be simplified to $\left(\frac{1}{7}\right)$ because $15\equiv 1(\mathrm{mod}7)$, which is trivially $1$. Skipping this step leads to needlessly complex calculations.
4. Overlooking the conditions for the supplementary laws. The second supplementary law for $\left(\frac{2}{p}\right)$ depends on $p$ modulo $8$, not modulo $4$. Confusing these conditions will yield an incorrect sign half the time.

Summary

• A quadratic residue modulo an odd prime $p$ is an integer $a$ such that $x^2\equiv a(\mathrm{mod}p)$ has a solution. The Legendre symbol $\left(\frac{a}{p}\right)$ elegantly encodes this information as $1$, $-1$, or $0$.
• Euler's criterion, $a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p)$, provides a direct but computationally intense definition.
• The Law of Quadratic Reciprocity, combined with the two supplementary laws for $-1$ and $2$, provides an efficient algorithm for computing Legendre symbols without solving congruences or performing large exponentiations.
• The Jacobi symbol generalizes the notation and rules to odd composite denominators, enabling the same efficient algorithm. Crucially, a Jacobi symbol value of $1$ does not guarantee a quadratic residue exists modulo a composite number.
• This theory directly answers questions about which primes can be represented by simple quadratic forms like $x^2+y^2$, linking the solvability of a quadratic congruence to the structure of the prime numbers themselves.