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.

-
Congruent numbers are equivalent,hence not distinct. – lab bhattacharjee Jan 20 '13 at 11:55

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

-
Is the contradiction because: if $p|i+j$, then $i \equiv (-j)$modp, and if $p|i-j$, then $i \equiv j$modp? – Traxter Jan 20 '13 at 11:57
I added the word distinct it was missing. – Amr Jan 20 '13 at 12:00
Aha! Many thanks Amr, I understand now. – Traxter Jan 20 '13 at 12:01

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

-

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.

-