A first surprise in elementary number theory is that solving a quadratic congruence is not just a matter of divisibility. The congruence $x^2 \equiv 1 \pmod{p}$ always has the two familiar solutions $x \equiv \pm 1 \pmod{p}$ when $p$ is an odd prime, but the congruence $x^2 \equiv 2 \pmod{p}$ changes its behaviour as $p$ changes. It is soluble modulo $7$, since $3^2 \equiv 2 \pmod{7}$, and insoluble modulo $5$, since the non-zero squares modulo $5$ are only $1$ and $4$. Quadratic residues isolate exactly this phenomenon: which non-zero residue classes modulo an odd prime are squares?

The question matters because quadratic congruences are the first place where arithmetic modulo primes develops a visible internal geometry. The non-zero residue classes modulo $p$ form a finite multiplicative group, and the square map folds that group in half. [Quadratic reciprocity](/theorems/1721), primality tests, finite fields, and elementary cryptography all begin with understanding that fold.

[example: The First Failure of Naive Square Roots] Let $p=11$. To find the non-zero square classes modulo $11$, it is enough to square the representatives $1,2,3,4,5,6,7,8,9,10$ and reduce each result modulo $11$. The first five give \begin{align*} 1^2 = 1 \equiv 1 \pmod{11}. \end{align*} \begin{align*} 2^2 = 4 \equiv 4 \pmod{11}. \end{align*} \begin{align*} 3^2 = 9 \equiv 9 \pmod{11}. \end{align*} \begin{align*} 4^2 = 16 = 11+5 \equiv 5 \pmod{11}. \end{align*} \begin{align*} 5^2 = 25 = 2\cdot 11+3 \equiv 3 \pmod{11}. \end{align*} The remaining non-zero classes repeat these values because each is the negative of one of the first five classes modulo $11$, and $(-x)^2=x^2$. Explicitly, \begin{align*} 6 \equiv -5 \pmod{11}, \quad 6^2 \equiv (-5)^2 = 25 \equiv 3 \pmod{11}. \end{align*} \begin{align*} 7 \equiv -4 \pmod{11}, \quad 7^2 \equiv (-4)^2 = 16 \equiv 5 \pmod{11}. \end{align*} \begin{align*} 8 \equiv -3 \pmod{11}, \quad 8^2 \equiv (-3)^2 = 9 \pmod{11}. \end{align*} \begin{align*} 9 \equiv -2 \pmod{11}, \quad 9^2 \equiv (-2)^2 = 4 \pmod{11}. \end{align*} \begin{align*} 10 \equiv -1 \pmod{11}, \quad 10^2 \equiv (-1)^2 = 1 \pmod{11}. \end{align*} Therefore the non-zero squares modulo $11$ are exactly $1,3,4,5,9$. The remaining non-zero classes $2,6,7,8,10$ are not squares modulo $11$, so the phrase "take a square root modulo $p$" hides a genuine existence question. [/example]

The computation also shows the basic symmetry: $x$ and $-x$ have the same square, and no other duplication occurs among non-zero classes modulo a prime. The theory of quadratic residues turns this symmetry into a test, then into a reciprocity law comparing primes.

## Definition

The main definition is designed to record solvability of one very specific congruence. We restrict to odd primes because modulo $2$ the distinction collapses, and we require $p \nmid a$ when speaking of residue versus non-residue so that the zero class does not obscure the multiplicative structure.

[definition: Quadratic Residue] Let $p$ be an odd prime and let $a \in \mathbb{Z}$ with $p \nmid a$. The integer $a$ is a quadratic residue modulo $p$ if there exists $x \in \mathbb{Z}$ such that \begin{align*} x^2 \equiv a \pmod{p}. \end{align*} The integer $a$ is a quadratic non-residue modulo $p$ if no such $x \in \mathbb{Z}$ exists. [/definition]

The definition depends only on the residue class of $a$ modulo $p$. If $a \equiv b \pmod{p}$ and $p \nmid a$, then the congruences $x^2 \equiv a \pmod{p}$ and $x^2 \equiv b \pmod{p}$ have the same solutions modulo $p$. For this reason we often speak about a non-zero class in $\mathbb{Z}/p\mathbb{Z}$ being a square.

The next notation packages the yes-or-no answer into a multiplicative symbol. It is useful because products of residues behave predictably, and the symbol turns that behaviour into ordinary multiplication of signs.

[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 \{-1,0,1\}. \end{align*} Its input-to-output rule is: for $a \in \mathbb{Z}$, the value $\left(\frac{a}{p}\right)$ is $0$ if $p \mid a$, is $1$ if $p \nmid a$ and $a$ is a quadratic residue modulo $p$, and is $-1$ if $p \nmid a$ and $a$ is a quadratic non-residue modulo $p$. [/definition]

The value $0$ is included for arithmetic convenience; the residue/non-residue distinction itself concerns the non-zero classes. With this convention the Legendre symbol is defined for every integer $a$, while the phrase quadratic residue still means a non-zero square class unless the zero class is explicitly mentioned.

The integer definition is perfect for congruence equations, but it hides the algebraic object doing the work. Passing to residue classes lets us see the square classes as the image of a specific self-map of the unit group.

[definition: Square Map Modulo $p$] Let $p$ be an odd prime. The square map modulo $p$ is the function \begin{align*} s_p: (\mathbb{Z}/p\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times. \end{align*} For each $\bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times$, its value is \begin{align*} s_p(\bar{x}) = \bar{x}^2. \end{align*} [/definition]

This map is a [group homomorphism](/page/Group%20Homomorphism) because multiplication in the unit group respects squaring. Naming its domain and codomain matters: we are not squaring arbitrary integers, but squaring invertible residue classes and staying inside the same finite group. Once the map is visible, the original solvability question becomes an image-membership question: given a non-zero class $\bar{a}$, is $\bar{a}$ hit by $s_p$? The next definition names exactly those classes, so later counting and subgroup arguments can refer to the image rather than repeatedly unpacking the congruence $x^2 \equiv a \pmod{p}$.

[definition: Square Class Modulo $p$] Let $p$ be an odd prime. A square class in $(\mathbb{Z}/p\mathbb{Z})^\times$ is an element $\bar{a} \in (\mathbb{Z}/p\mathbb{Z})^\times$ for which there exists $\bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times$ satisfying \begin{align*} \bar{x}^2 = \bar{a}. \end{align*} [/definition]

This is the same notion as a quadratic residue, expressed in the multiplicative group. The advantage is that the square map is now a group homomorphism, so counting and multiplicativity become consequences of group structure.

## The Square Map Modulo a Prime

### Counting Square Classes

The first structural question is how many residues there are. The example modulo $11$ suggested half of the non-zero classes are squares. That is not a coincidence; it follows from the fact that $x$ and $-x$ are the only non-zero roots of the same square congruence modulo a prime.

[quotetheorem:1714]