0
$\begingroup$

Prove or find a counterexample: Let p be a prime, and a and b positive integers. If a^2 ≡ b^2 (mod p) then a ≡ b (mod p).

I know that: If a and b are integers, we say that they are congruent modulo d iff b − a is a multiple of d. Equivalently, a and b are congruent mod d iff a (mod d) = b (mod d). Rewrite this as: a ≡ b (mod d).

I also know if p is prime, then GCD(a, p) = 1, GCD(b, p) = 1, but I'm not entirely sure if any of this information is useful or not

$\endgroup$
  • $\begingroup$ $(-1)^2 \equiv 1^2 \mod p \kern.6em\not\kern -.6em \implies -1 \equiv 1 \mod p$. $\endgroup$ – user137731 Oct 6 '15 at 2:29
  • $\begingroup$ @Bye_World Well, that's true if $p$ is an odd prime. If $p=2$ then the statement is true. $\endgroup$ – CIJ Oct 6 '15 at 2:32
  • $\begingroup$ @C.I.J. Meaning in general (which is the way the question is worded) the statement is false. $\endgroup$ – user137731 Oct 6 '15 at 2:33
0
$\begingroup$

Think about it this way, if $a^2 \equiv b^2 (p)$ then we must also have that $a^2-b^2 \equiv 0 (p)$.

If you can answer the following questions you should obtain your answer:

Can we factor $a^2-b^2$?

What does $p$ being prime tell us about it ability to divide the factors of $a^2-b^2$?

$\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.