# Prove: If $p$ is an odd prime and $a,b$ are any two integers with $0 \leq a < b \leq (p-1)/2$, then $a^2 \not\equiv b^2 \pmod{p}$.

The Problem

I am currently working on the following question:

If $p$ is an odd prime (i.e., $p \neq 2$) and $a,b$ are any two integers with $0 \leq a < b \leq (p-1)/2$, then $a^2 \not\equiv b^2 > \pmod{p}$.

I should note that this question is the second step in a multi-part problem. The first step asks to prove the following:

If $p$ is prime and $a^2 \equiv b^2 \pmod{p}$, then either $a \equiv b > \pmod{p}$ or $a \equiv -b \pmod{p}$.

To this, I offered the following proof:

Proof. Suppose that $p$ is prime and $a^2\equiv b^2 \pmod p$. We then have for some integer, say $k$, $$\frac{a^2-b^2}{k}=\frac{(a-b)(a+b)}{k}=p.$$ Setting $x=(a-b)$ and $y=(a+b)$, we see that $p|xy$. By the theorem provided in the hint, we have $p|x$ or $p|y$. If $p|x=a-b$ then we have $a\equiv b \pmod p$. Similarly, if $p|y=a+b$, we have $a\equiv -b \pmod p$. Thus, either $a\equiv b \pmod p$ or $a \equiv -b \pmod p$.

My Questions

1. First and foremost, is my proof for the previous step sufficient/correct?
2. Secondly, assuming my previous work is all squared away, where should I begin with this proof? I'm assuming I should use the previous step in some sort of manner, but I'm just not seeing it. My only idea was a proof by contradiction, but I'm not sure how I would start that one either...

As always, thank you all for your help and support!

• Hint $\ 0 < b\!-\!a < b\!+\!a\le 2(p\!-\!1)/2 = p\!-\!1$ so both are too small to be divisible by $p\ \$ – Bill Dubuque Jun 28 '17 at 14:24

1. Your proof of the second statement is correct.

2. Right, by contradiction. Suppose that $a^2 \equiv b^2 \bmod{p}$. Then, by your second statement, you know that either $a\equiv b\pmod{p}$ (i.e., they are the same number mod $p$) or $a\equiv -b\pmod{p}$: in this case, is it possibile that $0\le a<b\le \frac{p-1}{2}$?

• Really makes sense when you put it like that. Thank you! – Thy Art is Math Jun 28 '17 at 14:21
• You're welcome :) Note that this proves that there are exactly $(p-1)/2$ (non-zero) quadratic residues modulo $p$. – Paolo Leonetti Jun 28 '17 at 14:23