[proofplan]
We present two independent proofs. The first analyses the squaring map $\sigma: (\mathbb{Z}/p\mathbb{Z})^\times \to (\mathbb{Z}/p\mathbb{Z})^\times$, $x \mapsto x^2$, showing that it is exactly two-to-one because the only solutions of $x^2 \equiv y^2$ are $x \equiv \pm y$ and $\pm 1$ are distinct mod an odd prime. Hence its image has $(p-1)/2$ elements. The second proof fixes a primitive root $g$ and identifies the squares with the even powers of $g$, which are exactly half of the $p - 1$ powers.
[/proofplan]
[step:Define the squaring map on $(\mathbb{Z}/p\mathbb{Z})^\times$]
Consider the map
\begin{align*}
\sigma: (\mathbb{Z}/p\mathbb{Z})^\times &\to (\mathbb{Z}/p\mathbb{Z})^\times \\
x &\mapsto x^2.
\end{align*}
Well-definedness: $(\mathbb{Z}/p\mathbb{Z})^\times$ is a multiplicative group, so $x^2$ is a unit whenever $x$ is. The image of $\sigma$ is precisely the set of non-zero quadratic residues mod $p$:
\begin{align*}
\operatorname{Im}(\sigma) = \{a \in (\mathbb{Z}/p\mathbb{Z})^\times : a \equiv x^2 \pmod{p} \text{ for some } x\}.
\end{align*}
Since $0$ is not a quadratic residue in the usual convention counted here (we count residues among the $(p-1)$ units), proving $|\operatorname{Im}(\sigma)| = (p-1)/2$ is exactly the theorem.
[/step]
[step:Show that $\sigma$ is two-to-one via the identity $x^2 - y^2 = (x-y)(x+y)$]
Fix $a \in \operatorname{Im}(\sigma)$; we count $\sigma^{-1}(a) = \{x \in (\mathbb{Z}/p\mathbb{Z})^\times : x^2 \equiv a \pmod{p}\}$.
Pick any $y \in \sigma^{-1}(a)$. For $x \in (\mathbb{Z}/p\mathbb{Z})^\times$,
\begin{align*}
x^2 \equiv a \equiv y^2 \pmod{p} \iff p \mid x^2 - y^2 \iff p \mid (x-y)(x+y).
\end{align*}
Since $p$ is prime, by the [Prime Divisibility Lemma](/theorems/1698), $p \mid (x - y)$ or $p \mid (x + y)$, i.e., $x \equiv y$ or $x \equiv -y \pmod{p}$. Therefore
\begin{align*}
\sigma^{-1}(a) = \{y, -y\} \subseteq (\mathbb{Z}/p\mathbb{Z})^\times.
\end{align*}
These two elements are distinct: $y \equiv -y \pmod{p}$ would imply $2y \equiv 0 \pmod{p}$, and since $p$ is odd we have $\gcd(2, p) = 1$, forcing $y \equiv 0 \pmod{p}$, which contradicts $y \in (\mathbb{Z}/p\mathbb{Z})^\times$. Hence $|\sigma^{-1}(a)| = 2$ for every $a \in \operatorname{Im}(\sigma)$.
[guided]
We want to count the preimage $\sigma^{-1}(a)$ for a given $a$ in the image. Fix some $y$ with $y^2 \equiv a \pmod p$; such a $y$ exists because $a \in \operatorname{Im}(\sigma)$. The question becomes: for which $x$ does $x^2 \equiv y^2 \pmod{p}$ hold?
The standard algebraic identity
\begin{align*}
x^2 - y^2 = (x - y)(x + y)
\end{align*}
turns the congruence into a divisibility condition: $p \mid (x - y)(x + y)$. Here is the critical use of primality. Over a general ring the factorisation $(x-y)(x+y) = 0$ does not imply one factor is zero (think $\mathbb{Z}/8\mathbb{Z}$: $3^2 = 1^2 = 1$, but also $5^2 = 1$ and $7^2 = 1$, four square roots of $1$). Over $\mathbb{Z}/p\mathbb{Z}$ we use the [Prime Divisibility Lemma](/theorems/1698), which applies because $p$ is prime: $p \mid (x-y)(x+y)$ forces $p \mid x-y$ or $p \mid x+y$. Therefore
\begin{align*}
\sigma^{-1}(a) = \{y, -y\} \pmod{p}.
\end{align*}
Are these genuinely two distinct elements, or could $y$ equal $-y$ mod $p$? Equality $y \equiv -y \pmod p$ is equivalent to $p \mid 2y$. Since $\gcd(2, p) = 1$ (this is precisely where we use that $p$ is an **odd** prime), Euclid's lemma gives $p \mid y$, forcing $y \equiv 0 \pmod p$, which contradicts $y \in (\mathbb{Z}/p\mathbb{Z})^\times$. So $y \not\equiv -y$, and the preimage has exactly two elements.
Where exactly did oddness enter? Only at the step $p \nmid 2$. The theorem is genuinely false for $p = 2$: in $(\mathbb{Z}/2\mathbb{Z})^\times = \{1\}$, the single element is its own square, so the "count" $(p-1)/2 = 1/2$ is not even an integer. The hypothesis that $p$ is odd is essential.
[/guided]
[/step]
[step:Count the image by partitioning the domain into fibres]
Since $\sigma$ is two-to-one onto its image, the domain $(\mathbb{Z}/p\mathbb{Z})^\times$ partitions into $|\operatorname{Im}(\sigma)|$ fibres, each of size $2$:
\begin{align*}
|(\mathbb{Z}/p\mathbb{Z})^\times| = \sum_{a \in \operatorname{Im}(\sigma)} |\sigma^{-1}(a)| = 2 \cdot |\operatorname{Im}(\sigma)|.
\end{align*}
Since $|(\mathbb{Z}/p\mathbb{Z})^\times| = p - 1$, we conclude
\begin{align*}
|\operatorname{Im}(\sigma)| = \frac{p - 1}{2}.
\end{align*}
This is the number of non-zero quadratic residues mod $p$.
[/step]
[step:Alternative proof via a primitive root]
We record a second proof as an independent verification. By the theorem that [$(\mathbb{Z}/p\mathbb{Z})^\times$ is Cyclic](/theorems/1710), there exists a generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^\times$, so
\begin{align*}
(\mathbb{Z}/p\mathbb{Z})^\times = \{1, g, g^2, \ldots, g^{p-2}\},
\end{align*}
with these $p - 1$ elements pairwise distinct. An element $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ is a quadratic residue iff $a = x^2$ for some $x \in (\mathbb{Z}/p\mathbb{Z})^\times$. Writing $x = g^k$ with $0 \le k \le p - 2$, we have $a = g^{2k}$. Hence
\begin{align*}
\{\text{quadratic residues}\} = \{g^{2k} \bmod p^{p-1} : 0 \le k \le p - 2\} = \{g^{2k \bmod (p-1)} : 0 \le k \le p - 2\}.
\end{align*}
As $k$ ranges over $\{0, 1, \ldots, p-2\}$, the exponent $2k \bmod (p-1)$ ranges over the even residues mod $p - 1$. Since $p - 1$ is even (as $p$ is odd), the even residues are exactly $\{0, 2, 4, \ldots, p - 3\}$, giving $(p-1)/2$ distinct values. The corresponding elements $g^0, g^2, g^4, \ldots, g^{p-3}$ are pairwise distinct because distinct exponents mod $p - 1$ give distinct powers of $g$.
Thus the number of quadratic residues is $(p - 1)/2$, in agreement with the first proof.
[/step]
