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$.
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.