[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)$.[/step]

[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: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]