# What is the distribution of $x^2\pmod p$ where $p$ is a prime number, and $x \in \mathbb{Z_p}$?

Let $p$ be a prime number. How will numbers get distributed in $\mathbb{Z_{p}}$ upon doing $x^2 \pmod p$ where $x \in [0,p]$ is an integer?

My approach: Let $p = 97$. Then, $x^2 \equiv (97-x)^2 \pmod{97}$ (where $x$ is an integer less than $97$) because:

$$(97-x)^2 \equiv (97^2+x^2-2\cdot97\cdot x) \equiv x^2 \pmod{97}$$

So, I am sure that half, or less than half (let it be $N$), of the numbers of $\mathbb{Z_{97}}$ will get distributed. Also out of these two possibilities I have this intuition that this number $N$ would be half $(\frac{97-1}{2}+1)$, but I need to support my intuition with a proper proof.

Example: The values of $x^2 \pmod{97}$ are (for numbers 1 through 96): $$1,4,9,16,25,36,49,64,81,3,..................,3,81,64,49,36,25,16,9,4,1$$

Please help me to prove or disprove my intuition for any $p$.

• Good intuition! Note that $x^2$ and $y^2$ are identical mod $p$ iff $p$ divides $x^2-y^2 = (x-y)(x+y)$. This is in turn equivalent to $p$ dividing at least one of $x-y$ or $x+y$, in other words, $x\equiv \pm y \pmod p$. That means all the values $0^2,1^2,\ldots,48^2$ are distinct. – Erick Wong Apr 23 '17 at 1:43
• If you know a little group theory, this post may be useful. – André 3000 Apr 23 '17 at 1:53

Let $p$ be an odd prime, with $p = 2n+1$. Then we want to show that all of $1^2, 2^2, \ldots, n^2$ are distinct modulo $p$.
So it's enough to show that if $1 \le a < b \le n$, then $b^2 - a^2$ is not divisible by $p$. Now $b^2 - a^2 = (b-a)(b+a)$. But $b-a$ and $b+a$ are both positive and less than $p$, so they can't be divisible by $p$. So $b^2 - a^2$ isn't divisible by $p$. (Note that if $p$ is not prime, this breaks down! For example if $p = 15$ then we have $7^2 - 2^2 = (7-2)(7+2) = 5 \times 9 = 45$.)
So no two of $1^2, 2^2 \ldots, n^2$ are congruent mod $p$, and therefore they are $n$ different numbers, as you wanted.