# Modulus Congruence

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

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

## 1 Answer

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$?