2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Hint $\ 0 < b\!-\!a < b\!+\!a\le 2(p\!-\!1)/2 = p\!-\!1 $ so both are too small to be divisible by $p\ \ $ $\endgroup$ – Bill Dubuque Jun 28 '17 at 14:24
2
$\begingroup$
  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}$?

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