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).

1 Answer | Add Yours

justaguide's profile pic

justaguide | College Teacher | (Level 2) Distinguished Educator

Posted on

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)

We’ve answered 318,911 questions. We can answer yours, too.

Ask a question