3
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .