[proofplan]
We split into the three cases encoded by the [Legendre symbol](/page/Legendre%20Symbol): $p \mid a$, $p \nmid a$ with $a$ a [quadratic residue](/page/Quadratic%20Residue) modulo $p$, and $p \nmid a$ with $a$ a quadratic nonresidue modulo $p$. In the zero case, the only square root is the zero residue class. In the residue case, a chosen square root $\bar{r}$ gives exactly the two roots $\bar{r}$ and $-\bar{r}$, using that $\mathbb{Z}/p\mathbb{Z}$ is an [integral domain](/page/Integral%20Domain) and that $p$ is odd. In the nonresidue case, the definition gives no roots, and the three counts match $1+\left(\frac{a}{p}\right)$.
[/proofplan]
[step:Reduce the count to the three Legendre symbol cases]
Let
\begin{align*}
S := \{\bar{x} \in \mathbb{Z}/p\mathbb{Z} : \bar{x}^2 = \bar{a}\}
\end{align*}
denote the set of residue classes solving the congruence. By the definition of the Legendre symbol, the value $\left(\frac{a}{p}\right)$ is $0$ if $p \mid a$, is $1$ if $p \nmid a$ and $\bar{a}$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$, and is $-1$ if $p \nmid a$ and $\bar{a}$ is not a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. It is therefore enough to show that $|S|$ is respectively $1$, $2$, and $0$ in these three cases.
[/step]
[step:Show that the zero residue has exactly one square root]
Assume first that $p \mid a$. Then $\bar{a}=\bar{0}$ in $\mathbb{Z}/p\mathbb{Z}$. If $\bar{x} \in S$, then
\begin{align*}
\bar{x}^2=\bar{0}.
\end{align*}
Since $p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ is an integral domain, so $\bar{x}^2=\bar{0}$ implies $\bar{x}=\bar{0}$. Conversely, $\bar{0}^2=\bar{0}=\bar{a}$, so $\bar{0} \in S$. Hence
\begin{align*}
|S|=1.
\end{align*}
In this case $\left(\frac{a}{p}\right)=0$, and therefore
\begin{align*}
|S|=1=1+\left(\frac{a}{p}\right).
\end{align*}
[/step]
[step:Show that a nonzero quadratic residue has exactly two square roots]
Assume that $p \nmid a$ and that $\bar{a}$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. Choose $\bar{r} \in (\mathbb{Z}/p\mathbb{Z})^\times$ such that
\begin{align*}
\bar{r}^2=\bar{a}.
\end{align*}
Then $\bar{r} \in S$ and $-\bar{r} \in S$. These two classes are distinct: if $\bar{r}=-\bar{r}$, then $2\bar{r}=\bar{0}$; since $p$ is odd, $\bar{2}\ne \bar{0}$ and hence $\bar{r}=\bar{0}$ in the field $\mathbb{Z}/p\mathbb{Z}$, contradicting $\bar{r} \in (\mathbb{Z}/p\mathbb{Z})^\times$.
Now let $\bar{x} \in S$. Then
\begin{align*}
\bar{x}^2=\bar{a}=\bar{r}^2.
\end{align*}
Subtracting $\bar{r}^2$ and factoring in the commutative ring $\mathbb{Z}/p\mathbb{Z}$ gives
\begin{align*}
(\bar{x}-\bar{r})(\bar{x}+\bar{r})=\bar{0}.
\end{align*}
Because $\mathbb{Z}/p\mathbb{Z}$ is an integral domain, either $\bar{x}-\bar{r}=\bar{0}$ or $\bar{x}+\bar{r}=\bar{0}$. Thus $\bar{x}=\bar{r}$ or $\bar{x}=-\bar{r}$. Hence
\begin{align*}
S=\{\bar{r},-\bar{r}\}
\end{align*}
and so $|S|=2$.
[guided]
Assume that $p \nmid a$ and that $\bar{a}$ is a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. By the meaning of "square" in the unit group, there exists a unit $\bar{r} \in (\mathbb{Z}/p\mathbb{Z})^\times$ satisfying
\begin{align*}
\bar{r}^2=\bar{a}.
\end{align*}
This immediately gives two candidate solutions: $\bar{r}$ and $-\bar{r}$, since
\begin{align*}
(-\bar{r})^2=\bar{r}^2=\bar{a}.
\end{align*}
We must check that these are genuinely two different residue classes. If $\bar{r}=-\bar{r}$, then adding $\bar{r}$ to both sides gives
\begin{align*}
2\bar{r}=\bar{0}.
\end{align*}
Since $p$ is odd, the residue class $\bar{2}$ is nonzero in $\mathbb{Z}/p\mathbb{Z}$, and because $p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ is a field. Multiplying by the inverse of $\bar{2}$ gives $\bar{r}=\bar{0}$, contradicting the fact that $\bar{r}$ is a unit. Therefore $\bar{r}$ and $-\bar{r}$ are distinct.
It remains to prove that no other solutions exist. Let $\bar{x} \in S$ be any solution. Then $\bar{x}^2=\bar{a}$, while $\bar{r}^2=\bar{a}$ by construction, so
\begin{align*}
\bar{x}^2=\bar{r}^2.
\end{align*}
Subtracting $\bar{r}^2$ from both sides and using the difference-of-squares factorization in the commutative ring $\mathbb{Z}/p\mathbb{Z}$ gives
\begin{align*}
(\bar{x}-\bar{r})(\bar{x}+\bar{r})=\bar{0}.
\end{align*}
The crucial property is that $\mathbb{Z}/p\mathbb{Z}$ has no zero divisors, because $p$ is prime. Hence one factor must vanish:
\begin{align*}
\bar{x}-\bar{r}=\bar{0}
\end{align*}
or
\begin{align*}
\bar{x}+\bar{r}=\bar{0}.
\end{align*}
Thus $\bar{x}=\bar{r}$ or $\bar{x}=-\bar{r}$. Therefore the full solution set is
\begin{align*}
S=\{\bar{r},-\bar{r}\},
\end{align*}
and it has exactly two elements.
[/guided]
In this case $\left(\frac{a}{p}\right)=1$, and therefore
\begin{align*}
|S|=2=1+\left(\frac{a}{p}\right).
\end{align*}
[/step]
[step:Show that a quadratic nonresidue has no square roots]
Assume that $p \nmid a$ and that $\bar{a}$ is not a square in $(\mathbb{Z}/p\mathbb{Z})^\times$. If there were some $\bar{x} \in S$, then $\bar{x}^2=\bar{a}$. Since $\bar{a}\ne \bar{0}$, this would force $\bar{x}\ne \bar{0}$, so $\bar{x} \in (\mathbb{Z}/p\mathbb{Z})^\times$. Hence $\bar{a}$ would be a square in $(\mathbb{Z}/p\mathbb{Z})^\times$, contradicting the assumption. Therefore
\begin{align*}
S=\varnothing
\end{align*}
and $|S|=0$. In this case $\left(\frac{a}{p}\right)=-1$, so
\begin{align*}
|S|=0=1+\left(\frac{a}{p}\right).
\end{align*}
[/step]
[step:Combine the three cases to obtain the formula]
The three possible Legendre symbol cases have been exhausted. In the case $p \mid a$, the number of solutions is $1=1+\left(\frac{a}{p}\right)$. In the nonzero quadratic residue case, the number of solutions is $2=1+\left(\frac{a}{p}\right)$. In the quadratic nonresidue case, the number of solutions is $0=1+\left(\frac{a}{p}\right)$. Hence for every $a \in \mathbb{Z}$,
\begin{align*}
|S|=1+\left(\frac{a}{p}\right),
\end{align*}
which is the desired statement.
[/step]
