Question

give an example to show that a^2 congruent to b^2 mod n need not imply that a congruent to b mod n.

Answer 1

I think you mean that a does not have to be congruent to plus or minus b, otherwise the problem is rather trivial.

You can construct an example as follows. If, Mod n, we have

a^2 = b^2

then that means that:

(a-b)(a+b) = 0

This then does not mean that one of the two factors must be zero as it is possible that a-b and a + b have divisors in common with n, such that upon multiplication, you get a multiple of n making it zero Mod n.

If n = 100, then we have, e.g.:

10*20 = 0 -------->

(15 - 5)*(15 + 5) = 0 ---->

15^2 = 5^2

Yet modulo 100, 15 is not 5 nor is it
-5.

Answer 2

I don't get it