Suppose we want to solve $x^2 \equiv a \pmod p$, where $p$ is an odd prime. For $p=7$ we can list all squares, but for a large prime this becomes a search without structure. The Legendre symbol is the device that turns the question "is $a$ a square modulo $p$?" into a multiplicative arithmetic function.

The striking point is that being a square modulo $p$ is not merely a yes-or-no property. Among the non-zero residue classes, it is compatible with multiplication: two non-zero non-squares multiply to a square, a square times a non-square remains a non-square, and this pattern is exactly what the values $1$ and $-1$ record.

[example: Squares Modulo $7$] Modulo $7$, we square each residue class representative $0,1,2,3,4,5,6$ and reduce the result modulo $7$: \begin{align*} 0^2=0 \equiv 0 \pmod 7, \quad 1^2=1 \equiv 1 \pmod 7, \quad 2^2=4 \equiv 4 \pmod 7, \quad 3^2=9 \equiv 2 \pmod 7. \end{align*} \begin{align*} 4^2=16 \equiv 2 \pmod 7, \quad 5^2=25 \equiv 4 \pmod 7, \quad 6^2=36 \equiv 1 \pmod 7. \end{align*} Thus the square classes modulo $7$ are exactly $0,1,2,4$. Excluding the zero class, the non-zero square classes are $1,2,4$, while the remaining non-zero classes $3,5,6$ are non-squares. Therefore $x^2 \equiv 2 \pmod 7$ has solutions, for example $x \equiv 3$ and $x \equiv 4 \pmod 7$, but $x^2 \equiv 3 \pmod 7$ has no solution because $3$ does not occur in the square table. [/example]

This example shows the basic failure of brute force. A table answers one prime at one time, but it does not explain how square classes behave under multiplication or how to compare different primes. The first step is to name the square condition itself.

## Quadratic Residues and Non-Residues

A [quadratic residue](/page/Quadratic%20Residue) is what appears in a square table modulo $p$. The definition is phrased using integers, but the condition depends only on residue classes modulo $p$. It captures the local square question that the whole page studies.

[definition: Quadratic Residue Modulo an Odd Prime] Let $p$ be an odd prime. The quadratic-residue predicate modulo $p$ is the function \begin{align*} R_p: \mathbb{Z} &\to \{\text{true},\text{false}\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto R_p(a), \end{align*} where $R_p(a)=\text{true}$ if and only if there exists $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod p. \end{align*} An integer $a \in \mathbb{Z}$ is called a quadratic residue modulo $p$ if $R_p(a)=\text{true}$. [/definition]

This page uses the inclusive convention: multiples of $p$ count as quadratic residues because the congruence is solved by $x \equiv 0 \pmod p$. Many number-theory arguments reserve the phrase "quadratic residue" for non-zero square classes, so we will explicitly say "non-zero quadratic residue" whenever the zero class must be excluded.

The zero class satisfies the same equation with $x \equiv 0 \pmod p$, but it does not belong to the multiplicative group of non-zero residue classes. To discuss the failed square classes inside that group, we need a term that excludes multiples of $p$. This is the role of quadratic non-residue.

[definition: Quadratic Non-Residue Modulo an Odd Prime] Let $p$ be an odd prime. The quadratic-non-residue predicate modulo $p$ is the function \begin{align*} N_p: \mathbb{Z} &\to \{\text{true},\text{false}\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto N_p(a), \end{align*} where $N_p(a)=\text{true}$ if and only if $p \nmid a$ and there is no $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod p. \end{align*} An integer $a \in \mathbb{Z}$ is called a quadratic non-residue modulo $p$ if $N_p(a)=\text{true}$. [/definition]

## Definition

The next construction is needed because residue and non-residue terminology is too wordy for formulas. We want a single arithmetic function whose values can be multiplied, summed, and inserted into root-counting identities. The Legendre symbol is that function, with a special value for the zero class.

[definition: Legendre Symbol] Let $p$ be an odd prime. The Legendre symbol modulo $p$ is the function \begin{align*} \left(\frac{\cdot}{p}\right): \mathbb{Z} &\to \{0,1,-1\}. \end{align*} It is evaluated by the rule \begin{align*} a &\mapsto \left(\frac{a}{p}\right), \end{align*} where \begin{align*} \left(\frac{a}{p}\right)&=0 \quad \text{if } p \mid a. \end{align*} \begin{align*} \left(\frac{a}{p}\right)&=1 \quad \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue modulo } p. \end{align*} \begin{align*} \left(\frac{a}{p}\right)&=-1 \quad \text{if } a \text{ is a quadratic non-residue modulo } p. \end{align*} [/definition]

The symbol depends only on $a$ modulo $p$. It should be read as a function on residue classes, with the zero class separated because it is not invertible.

[example: Reading the Symbol Modulo $7$] Modulo $7$, the square table from the previous example is \begin{align*} 0^2 \equiv 0,\quad 1^2 \equiv 1,\quad 2^2 \equiv 4,\quad 3^2 \equiv 2,\quad 4^2 \equiv 2,\quad 5^2 \equiv 4,\quad 6^2 \equiv 1 \pmod 7. \end{align*} Thus the classes represented by squares are $0,1,2,4$. By the definition of the Legendre symbol, the zero class gives $\left(\frac{0}{7}\right)=0$, the non-zero square classes give \begin{align*} \left(\frac{1}{7}\right)=1,\quad \left(\frac{2}{7}\right)=1,\quad \left(\frac{4}{7}\right)=1, \end{align*} and the remaining non-zero classes $3,5,6$ give \begin{align*} \left(\frac{3}{7}\right)=-1,\quad \left(\frac{5}{7}\right)=-1,\quad \left(\frac{6}{7}\right)=-1. \end{align*} For a numerator outside the list $0,\dots,6$, first reduce it modulo $7$. Since $10-3=7$, we have $10 \equiv 3 \pmod 7$, so \begin{align*} \left(\frac{10}{7}\right)=\left(\frac{3}{7}\right)=-1. \end{align*} Also, $-3-4=-7$, so $-3 \equiv 4 \pmod 7$, and therefore \begin{align*} \left(\frac{-3}{7}\right)=\left(\frac{4}{7}\right)=1. \end{align*} The value of the symbol is therefore determined by the residue class of the numerator modulo $7$, with the zero class separated from the non-zero square and non-square classes. [/example]

## Residues as a Multiplicative Question

The non-zero residue classes modulo $p$ form the group $(\mathbb{Z}/p\mathbb{Z})^\times$. Squaring is a homomorphism on this group. This observation explains both how many non-zero squares there are and why the Legendre symbol is multiplicative.

### Half of the Non-Zero Classes

A square table has repetitions because $x$ and $-x$ have the same square. For an odd prime, those are the only repetitions among non-zero residue classes. Hence the non-zero classes split into two equal parts: among the $p-1$ non-zero classes, exactly half are squares and half are non-squares. With the page's inclusive convention, the zero class is still a quadratic residue, but it is not part of this equal non-zero split.

The equal split explains why the values $1$ and $-1$ occur equally often away from zero. Counting alone does not explain products. The structural reason is stronger: the non-zero square classes form a subgroup of $(\mathbb{Z}/p\mathbb{Z})^\times$ of index $2$, and multiplying by a fixed non-square swaps that subgroup with its complementary coset. Since products are the natural operation in $(\mathbb{Z}/p\mathbb{Z})^\times$, this subgroup picture also explains the computational rule for products: the symbol of a product is the product of the symbols.