Quadratic Residues Are Distinct I'm having a little trouble understanding the proof that the quadratic residues mod p, given by:
$1^2,2^2,...,(\frac{p-1}{2})^2$
are distinct.
So far I have this: If we have $j$ such that $\frac{p-1}{2}\le j\le p-1$, then the number $j^2$ must appear in the list $1^2, 2^2,...,(\frac{p-1}{2})^2$, since $p-j$ must have residue sitting in $1,2,...,(\frac{p-1}{2})$, and $j^2 \equiv (-j)^2 \equiv (p-j)^2$modp.
So I can see why the complete list of residues is $1^2, 2^2,...,(\frac{p-1}{2})^2$.
Now my trouble is how to prove that the $1^2, 2^2,...,(\frac{p-1}{2})^2$ are distinct. Could anybody give me a nudge in the right direction please?
Many thanks.
 A: Suppose there exists distinct $i,j\in\{1,2,...,\frac{p-1}{2}\}$ such that $i^2\equiv j^2$ (mod p), then $i^2-j^2\equiv (i+j)(i-j)\equiv 0$ (mod p). Thus, $p|(i+j)(i-j)$. Since $p$ is prime, therefore $p|i+j$ or $p|i-j$. Both of these statements lead to a contradiction. This is because since $i,j\in\{1,2,...,\frac{p-1}{2}\}$, therefore $2\leq i+j\leq p-1$ and $1\leq |i-j| \leq |i|+|j| \leq p-1$. no number in the set $\{1,2,...,p-1\}$ is divisible by $p$.
A: The ring of residue classes $\Bbb Z/\Bbb Zp$ is a field when $p$ is prime. As such, there are at most two classes with the same square, because the equation $X^2=a$ has at most two solutions in a field, whatever $a$.
Now observe that the elements $x$ and $-x$ do have the same square because $(-1)^2=1$. Thus the classes in $\Bbb Z/\Bbb Zp$ can be paired as follows:
$(1,-1)=(1,p-1)$, $(2,-2)=(2,p-2)$, $(3,-3)=(3,p-3)$and so on. It is obvious that no two classes in your list appear in the same pair and so they give distinct squares in $\Bbb Z/\Bbb Zp$.
A: Hint $\, $ If $\rm\ j^2 \equiv k^2\:$ for $\rm\,1\le j < k \le (p\!-\!1)/2\:$ then $\rm\:x^2 - j^2\,$ has $3$ distinct roots $\rm\:j < k < p\!-\!j \equiv -j\:$ contra a quadratic has at most two roots in a field.
