Prove that $x^2 \equiv a \bmod{p}$ has a solution for exactly half of the integers of $a$ satisfying $1 \le a \le p - 1$. Let $p$ be an odd prime.
I want to prove that $x^2 \equiv a \bmod{p}$ has a solution for exactly half of the integers of $a$ satisfying $1 \le a \le p - 1$.
Am I supposed to use $\gcd(2, p - 1)$ for my answer? If so, why?
 A: If $p$ is odd and $a \in \mathbb{Z}/p\mathbb{Z} \setminus \{0\}$ and $x^2 = a$ then $(-x)^2 = a$ and $x \ne -x$. So if the equation $x^2 = a$ has a solution, it has at least two distinct solutions.
Suppose that $x^2 = y^2 \mod p$ with $p$ prime. Then $(x-y) (x+y) = 0 \mod p$. Since $p$ is prime, this implies $x-y = 0 \mod p$ or $x+y = 0 \mod p$ ($\mathbb{Z}/p\mathbb{Z}$ is a field, which can be proved from the definition of prime numbers). Therefore, if the equation $x^2 = a$ has a solution, it has at most two solutions.
Combining these two lemmas, if the equation $x^2 = a$ has a solution, it has exactly two solutions. If $a \ne b$ then obviously the equations $x^2 = a$ and $y^2 = b$ have distinct solutions. The set $\mathbb{Z}/p\mathbb{Z} \setminus \{0\}$ can be expressed as the union of all the solutions of equations of these types: $\mathbb{Z}/p\mathbb{Z} \setminus \{0\} = \{x \mid x^2 = 1\} \cup \dots \cup \{x \mid x^2 = p-1\}$. Each of these sets contains exactly 2 elements, they are pairwise disjoint, and the union contains $p-1$ arguments. By cardinality arithmetic, there are exactly $(p-1)/2$ such sets. In other words, exactly half the elements of $\mathbb{Z}/p\mathbb{Z} \setminus \{0\}$ have exactly two square roots, and the others have none.
A: The multiplicative group $(\mathbb{Z}_p\setminus \{0\},\cdot)$ of the field $\mathbb{Z}_p$ is abelian and has size $(p-1)$. It is thus a direct sum of primary cyclic groups, i.e. $p_1,\ldots,p_N$ are the prime factors of $p-1 = p_1^{n_1}\ldots p_N^{n_N}$, then $$
  (\mathbb{Z}_p\setminus \{0\},\cdot) = \bigoplus_{i=1}^N C_{p_i^{n_i}} = \bigoplus_{i=1}^N(\mathbb{Z}_{p_i},+)
$$
Since $p$ is odd, $p-1$ is even, and thus $p_1 = 2$, $n_1 \geq 1$.
In $(\mathbb{Z}_{2^n}, +)$, $2x = a$ has a solution for every even $a$ (just take $\frac{a}{2}$), and no solution for odd $a$ (since then $2x - k2^n$ would need to be odd). Thus, there is a solution for every second element of $(\mathbb{Z}_{2^n}, +)$.
In $(\mathbb{Z}_{p^n}, +)$ for a prime $p > 2$, there is a solution for $2x = a$ for every $a$, since $2$ is coprime to $p^n$ then, and thus has an inverse.
Therefor, the solutions for $x^2 \equiv a$ in $(\mathbb{Z}_p\setminus \{0\},\cdot)$ are represented by the vectors $$
  (x_1,\ldots,x_N) \text{ where $0 \leq x_i < p_i^{n_i}$, $x_1$ even} \text{,}
$$
taken to be elements of $\bigoplus_{i=1}^N(\mathbb{Z}_{p_i},+)$.
