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.