$x^2$ modulo a prime 
Prove that $x^2$ modulo a prime $p>2$ takes on exactly $\dfrac{p+1}{2}$ different values.

I thought of first saying the residues modulo $p$ can be written as follows: $$0,1,\ldots,\frac{p+1}{2}-1,-\left(\frac{p+1}{2}-1\right),\ldots,-1.$$ Thus if it weren't the case that $x^2$ took on exactly $\dfrac{p+1}{2}$ different values modulo $p$, then there would exist $x_1 \neq x_2 $ such that $x_1,x_2 \leq \frac{p-1}{2}$ and $x_1^2 \equiv x_2^2 \pmod{p}$.
How do I prove a contradiction here?
 A: You can use the following:
Define $\varphi\colon (\mathbb{Z}/p\mathbb{Z})^\times\rightarrow (\mathbb{Z}/p\mathbb{Z})^\times$ by $\varphi(x)=x^2$. It is a homomorphism and thus it agrees with the first isomorphism theorem, so finding the cardinaluty of $\ker \varphi$ will give you the solution without $0$. 
So what are the elements satisfying $x^2=1$. $\mathbb{Z}/p\mathbb{Z}$ is actually a field and thus $x^2=1$ has at most 2 solutions. we know +1 and -1 are solutions so they are the onlt solutions.
Thus $|Im(\varphi) |=\frac{p-1}{2}$ and adding 0 back since $0^2=0$ you get $\frac{p+1}{2}$ elements
A: $x_1^2 \equiv x_2^2 \bmod{p}$ implies that $p$ divides $x_1-x_2$ or $x_1+x_2$. 
Since $x_1+x_2 < p$, we must have $x_1=-x_2$, which contradicts $x_1,x_2 \ge 0$.
Since $|x_1-x_2|\le x_1+x_2 < p$, we must have $x_1=x_2$, which contradicts $x_1 \ne x_2$.
A: Put everything on one side and factor to get the equivalent  $(x_1 - x_2)(x_1 + x_2) \equiv 0 \pmod{p}$. Since $p$ is prime, this implies $(x_1 - x_2) \equiv 0 \pmod{p}$ or $(x_1 + x_2) \equiv 0 \pmod{p}$. 
Yet both are impossible under your assumptions. 
However, note that this  only shows that there cannot be fewer than $(p+1)/2$ values. To show there are exactly $(p+1)/2$ proceed as above to note that the only way the squares can be equal for distinct $x_1,x_2$ with  $0\le x_1,x_2 \le p-1$ is $x_1 + x_2 = p$ that is for each non-zero $x_1$ there is exactly  one $x_2$ having the same square.
