[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$. In this case $\left(\frac{a}{p}\right)=1$, and therefore \begin{align*} |S|=2=1+\left(\frac{a}{p}\right). \end{align*}[/step]

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

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