Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Congruent numbers are equivalent,hence not distinct. –  lab bhattacharjee Jan 20 '13 at 11:55
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.