5
$\begingroup$

Given that: $p$ is an odd prime, $a\geq 1,b \leq \frac{p-1}{2}$, and that $a \not\equiv b \pmod p$, show that $a^2 \not\equiv b^2 \pmod p$

Based on the second condition, I know that $a + b < p$ is true, which I think should be helpful, but I'm not sure how to use this.

I also tried to use the fact that $p = 2k + 1$, but again, I didn't find any luck with this.

I'm very new with congruences, so I really appreciate any help!

$\endgroup$
1
  • $\begingroup$ I added the "elementary-number-theory" tag to your post. Cheers! $\endgroup$ – Robert Lewis Sep 3 '19 at 6:10
7
$\begingroup$

If $p\mid a^2-b^2=(a-b)(a+b)$, then $p\mid a+b$ or $p\mid a-b$ because it is prime. Now as you correctly noted $a+b\lt p$, so $p$ cannot divide $a+b$, therefore $p\mid a-b$; in other words $a\equiv b\pmod{p}$.

$\endgroup$
1
  • $\begingroup$ More precisely (or pedantically) $0<a+b<p$ so $p\not |\,(a+b)$.....+1 $\endgroup$ – DanielWainfleet Sep 3 '19 at 5:38
4
$\begingroup$

If

$a^2 \equiv b^2 \mod p \tag 1$

then

$a^2 - b^2 \equiv 0 \mod p, \tag 2$

or

$(a + b)(a - b) \equiv a^2 - b^2 \equiv 0 \mod p; \tag 3$

since

$1 \le a, b \le \dfrac{p - 1}{2}, \tag 4$

we have

$2 \le a + b \le 2\dfrac{p - 1}{2} = p - 1; \tag 5$

it follows that

$a + b \not \equiv 0 \mod p, \tag 6$

and hence that $a + b$ is invertible modulo $p$, since

$\Bbb Z_p = \Bbb Z / p\Bbb Z \tag 7$

forms a field, and $p$ is odd, so $2 \not \equiv 0 \mod p$; from this we conclude that

$a - b \equiv 0 \mod p, \tag 8$

or

$a \equiv b \mod p, \tag 9$

contrary to the hypothesis

$a \not \equiv b \mod p; \tag{10}$

therefore,

$a^2 \not \equiv b^2 \mod p, \tag{11}$

$OE\Delta$.

$\endgroup$
2
  • 2
    $\begingroup$ QED= quod erat demonstratum= which was to be demonstrated.... I am curious about what $OE\Delta$ abbreviates. I've never seen it. $\endgroup$ – DanielWainfleet Sep 3 '19 at 5:43
  • 2
    $\begingroup$ @DanielWainfleet: it's the abbreviation for $\omicron \pi \epsilon \rho \; \epsilon \delta \alpha \iota \; \delta \epsilon \xi \epsilon \iota$, Greek for our oft-appearing Latin "QED". I got tired of writing that all the time, so . . . see en.wikipedia.org/wiki/List_of_Greek_phrases. Cheers! $\endgroup$ – Robert Lewis Sep 3 '19 at 5:48
2
$\begingroup$

The idea is that $a^2-b^2=(a-b)(a+b)$ and saying $a^2 \not\equiv b^2 (mod p)$ is the same as saying, $(a-b)(a+b) \not\equiv 0 (mod p)$

You do have from your conditions that $a-b \not\equiv 0 (mod p)$ and since $a+b<p$ then ofcourse $a+b \not\equiv 0 (mod p)$ and $p$ is a prime so now you have that, $a^2 \not\equiv b^2 (mod p)$

$\endgroup$

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.