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 have difficulty solving a problem in my textbook. I'm hoping someone out there can help me out, so that I can understand this. The problem is listed below

Given that $p$ is an odd prime. Prove that the $\frac{p-1}{2}$ quadratic residues mod p are congruent to the following:

$$1^2, 2^2, 3^2, \space \ldots, \space (\frac{p-1}{2})^2$$

Any ideas on how to solve this would be great.

share|improve this question
    
What are your own thoughts? Where are you stuck? –  Tobias Kildetoft Mar 20 '13 at 17:36
    
Not really sure how to approach it, do you have any ideas of were to start? –  Samantha Smith Mar 20 '13 at 17:37
    
Well, do you see why it will be enough to show that those numbers are distinct? –  Tobias Kildetoft Mar 20 '13 at 17:39
    
I do not know why that'd be enough, why? –  Samantha Smith Mar 20 '13 at 17:40
    
Well, can you show that those numbers are in fact quadratic residues? –  Tobias Kildetoft Mar 20 '13 at 17:41

1 Answer 1

up vote 1 down vote accepted

Hint: These are obviously quadratic residues, and there are $\frac{p-1}{2}$ numbers in the list $1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2$.

You will be finished if you can show they are all distinct modulo $p$.

Suppose to the contrary that $a^2\equiv b^2\pmod{p}$, where $a$ and $b$ are distinct numbers in the interval from $1$ to $\frac{p-1}{2}$, with say $b\gt a$.

Then $p$ divides $(b-a)(b+a)$. Argue now that this is impossible, since $b-a$ and $b+a$ are too small.

share|improve this answer

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.