2
$\begingroup$

I'm trying to prove the following claim.

If $p$ is prime then $$|\{n^2 \pmod p\mid n \in [0, p-1]\}| = \frac{p+1}{2}$$

Where do I start? Would a proof by contradiction, contrapositive, or a direct proof be more intuitive than the other?

Thanks.

$\endgroup$
  • $\begingroup$ I don't want to be nit picky but $p=2$ is definitely a counter example $\endgroup$ – Stan Tendijck Feb 20 at 18:29
  • $\begingroup$ @StanTendijck the title does state that $p≥5$ but this seems to have been lost within the actual question... $\endgroup$ – Benjamin Feb 20 at 19:00
3
$\begingroup$

Clearly, $a^2$ and $b^2$ (wlog $a>b$) give the same residue modulo $p$ iff $$p\mid a^2-b^2 = (a-b)(a+b)\implies p\mid a-b \vee p\mid a+b$$

But since $0<a-b<p$ we must have $p\mid a+b$ so $a+b=p$. So for each $a\ne 0$ we have exactly one $b$ such that $a+b = p$ and thus the conclusion.

$\endgroup$
2
$\begingroup$

Idea $$n^2\mod p = (p - n)^2\mod p$$

$\endgroup$
  • $\begingroup$ I notice when I let $n = p-1$ that its the same as when $n=1$. Similarly for $n = p-k$ is equal to when $n = k$, but I'm not quite sure how to write this mathematically, or if I'm even on the right track. Intuitively I notice that the squares repeat halfway through with the exception of $0$, so that's why there are $\frac{p+1}{2}$ unique squares. But I'm still a bit confused. $\endgroup$ – jd94 Feb 20 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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