Prove with an example that a^2 is congruent to b^2 (mod n) need not imply that a is congruent to b (mod n).

If a^2 is congruent to b^2(mod n) it implies that a^2 -
b^2 is an integer multiple of n.

a is congruent to b(mod n)
implies that a - b is an integral multiple of n.

If a^2 -
b^2 is an integral multiple of n

=> (a^2 - b^2) =
k*n, where k is an integer

=> (a - b)(a + b) =
k*n

=> a - b = k*n/(a +
b)

k/(a + b) need not be an
integer

Therefore we cannot say that a^2 is congruent to
b^2 (mod n) implies that a is congruent to b (mod n)

Take
the case of 25 being congruent to 9(mod 4) as (25 - 9) = 16 is an integral multiple of
4.

5 is not congruent to 3(mod 4) as 4*4/(5 + 3) = 4/2 = 2
which is not an integral multiple of 4.

This
proves that a^2 is congruent to b^2 (mod n) does not imply that a is congruent to b (mod
n)