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

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.

Sure! Here's an example that demonstrates that \(a^2 \equiv b^2 \ \text{mod} \ n\) does not always imply \(a \equiv b \ \text{mod} \ n\):

Let's consider \(a = 2\), \(b = 3\), and \(n = 7\).

We have \(2^2 \equiv 4 \ \text{mod} \ 7\) and \(3^2 \equiv 9 \ \text{mod} \ 7\). Simplifying, we find that \(2^2 \equiv 4 \ \text{mod} \ 7\) and \(3^2 \equiv 2 \ \text{mod} \ 7\).

Although \(a^2 \equiv b^2 \ \text{mod} \ n\) holds true in this case, \(a \equiv b \ \text{mod} \ n\) does not hold. In fact, \(2 \not\equiv 3 \ \text{mod} \ 7\).

Therefore, the example demonstrates that \(a^2 \equiv b^2 \ \text{mod} \ n\) does not imply \(a \equiv b \ \text{mod} \ n\).

Sure! Let's consider the example where a = 4, b = 6, and n = 5.

To check if a^2 is congruent to b^2 modulo n, we need to compute the remainders of a^2 and b^2 when divided by n.

In this case, a^2 is equal to 4^2 = 16, and the remainder of 16 divided by 5 is 1. Similarly, b^2 is equal to 6^2 = 36, and the remainder of 36 divided by 5 is also 1.

So, we have a^2 ≡ 1 (mod 5) and b^2 ≡ 1 (mod 5), which satisfies the condition a^2 ≡ b^2 (mod n).

However, when we compare a and b separately modulo n, we find that the remainder of 4 divided by 5 is 4, while the remainder of 6 divided by 5 is 1.

Hence, we can conclude that a^2 ≡ b^2 (mod n) does not imply a ≡ b (mod n) in this example.

I don't get it