Why Is This Squared Modulo Prime Number Equation True?

Question

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.

@M47145 C represents the amount of unique outcomes - I updated my question to specify this — Nick Zuber, Apr 20 '16 at 01:32
@CarryonSmiling I'm afraid I'm unfamiliar with quadratic residues - would you mind clarifying? — Nick Zuber, Apr 20 '16 at 01:35
We say $a$ is a quadratic residue $\bmod m$ if there is a $k$ such that $k^2\equiv a \bmod m$. — Asinomás, Apr 20 '16 at 01:37

score 2 · Accepted Answer · answered Apr 20 '16 at 01:45

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.

This is beautiful and easy to digest, great answer! – Nick Zuber Apr 20 '16 at 01:49 — Nick Zuber, Apr 20 '16 at 01:49

score 0 · Answer 2 · answered Apr 20 '16 at 01:39

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.

Why Is This Squared Modulo Prime Number Equation True?

2 Answers2