Nonzero integers mod $p$ - showing exactly half are perfect squares

Question

I've been scratching my head lately over this question:

Suppose that $p$ is an odd prime number. An element $x$ of $\mathbb{Z}_p$ is called a perfect square in $\mathbb{Z}_p$ if there is an element $u$ in $\mathbb{Z}_p$ such that $x = u^2$. Show that exactly half of the nonzero elements of $\mathbb{Z}_p$ are perfect squares.

I didn't know what perfect squares meant, but after doing some independent research, the term can also be coined as "quadratic residues". How should one approach this question, keeping in mind that in need to show that exactly half of the nonzero elements of $\mathbb{Z}_p$ are perfect squares?

Answer 1

There are $p-1$ non-zero elements of $\mathbb{Z}_p$, and since $p$ is an odd prime, the number $p-1$ is even. Group these elements according to what their square is. For example, in $\mathbb{Z}_7$, we have $$1^2=1\qquad 2^2=4\qquad 3^2=2\qquad 4^2=2\qquad 5^2=4\qquad 6^2=1$$ and therefore we would group the six non-zero elements of $\mathbb{Z}_7$ into the three groups $$\underbrace{1,6}_{\text{square is 1}}\qquad \underbrace{2,5}_{\text{square is 4}}\qquad \underbrace{3,4}_{\text{square is 2}}$$ Note that the number of groups is equal to the number of perfect squares (since we grouped the elements precisely according to when their squares are the same).

Can you prove that, for any odd prime $p$, each of the groups has exactly two elements, and therefore that there are exactly $\frac{p-1}{2}$ groups?

Hint: In the familiar case of real numbers, if $x>0$, which two numbers are there whose square is $x$?

Answer 2

Map the set $S$ of nonzero elements of $\Bbb Z_p$ to the non-zero squares $S^{2}$ by $\varphi\colon x\mapsto x^2$. Each quadratic polynomial in a field has at most two roots, and actually $\varphi^{-1}(\varphi(x))=\{x,-x\}$.

Thus, by the Shepherd's principle, $$\Bigl\lvert S^2\Bigr\rvert=\frac{p-1}2\enspace\ \text{and}\quad \Bigl\lvert S\setminus S^{2}\Bigr\rvert=\frac{p-1}2.$$

Shepherds' principle:

Let $S,T$ be two sets and $f:S\longrightarrow T$ be a surjective map such that, for any $t\in T, \:\bigl|f^{-1}(t)\bigr|=n$. Then $$|X|=n\times|Y|.$$

Answer 3

If $x_2^2\equiv x_1^2\pmod p$ where $x_2\neq x_1\in(\Bbb Z/p\Bbb Z)^*=\{1,2,3,...,p-1\}$. Then $(x_2-x_1)(x_2+x_1)\equiv 0\pmod p$. This implies that $x_2+x_1=p$ and $x_2=p-x_1$! We are done. Aren't we?