Why Is This Squared Modulo Prime Number Equation True? I recently was trying to figure out if there was an simple way to tell how many unique outcomes can be produced from the following equation:
$k^2 \mod m$
where $m$ is some odd prime number and $k$ is some integer.
After running a series of brute tests, I was able to derive the following equation:
$C=$$(m+1)\over2$
where $C$ is the amount of unique outcomes.
From what I've tested, this equation I've derived works, however I'm a bit lost as to how I can prove such an equation is valid for all $m$. Has this already been proven somewhere? If not, any guidance or help towards a solution would be greatly appreciated.
 A: Your $C$ is correct.
Theorem.  If $m=2n+1$ is an odd prime number, then there are exactly $n+1$ different values of $k^2$ modulo $m$.
Proof.  All values (including possible repetitions) are
$$0^2,\ 1^2,\ 2^2,\ldots,\ n^2,\ (n+1)^2,\ldots,\ (2n-1)^2,\ (2n)^2\ .$$
Modulo $2n+1$ we have
$$\eqalign{(2n)^2&\equiv(-1)^2\equiv1^2\cr
  (2n-1)^2&\equiv(-2)^2\equiv2^2\cr
  &\vdots\cr
  (n+1)^2&\equiv(2n+1-(n+1))^2\equiv n^2\ ,\cr}$$
which reduces the list to
$$0^2,\ 1^2,\ 2^2,\ldots,\ n^2.$$
There are $n+1$ numbers in this list, so we have to prove that they are all different modulo $p=2n+1$.  If
$$a^2\equiv b^2$$
then
$$p\mid(a^2-b^2)$$
so
$$p\mid(a-b)(a+b)$$
and since $p$ is prime,
$$p\mid a-b\quad\hbox{or}\quad p\mid a+b\ .$$
But if $0\le a,b\le n$ then
$$-n\le a-b\le n\quad\hbox{and}\quad 0\le a+b\le2n\ .$$
So the only way that $p$ can divide $a-b$ is when $a-b=0$, and the only way that $p$ can divide $a+b$ is when $a=0$, $b=0$.  Therefore $a=b$.  So, different numbers from $0$ to $n$ have different squares, and this completes the proof.
A: Suppose that $m\equiv k^2$ is a quadratic residue mod $p$. (A quadratic residue is simply a number that is a square of another number mod $p$). It suffices to show that if $m\neq 0$, then there are exactly two $k$ such that $k^2\equiv m$. However, note that if $x^2\equiv m$, then $x^2-k^2 \equiv 0$, so $(x-k)(x+k) \equiv 0$, so either $x\equiv k$ or $x\equiv -k$, completing the proof.
