Thread: congruence and the Division Algorithm...

Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
where "=" means the equivalence.

I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

how do I do this one?

Thanks for any help!

Originally Posted by Vedicmaths

Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
where "=" means the equivalence.

I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

how do I do this one?

Thanks for any help!

.

Originally Posted by Vedicmaths

Disprove with the counter example: If a^2 = b^2 (mod n) then a=b (mod n)..
where "=" means the equivalence.

I think...since, n\a^2 - b^2...proceeds to n\(a-b)(a+b)...shows that n also divides (a-b)...so can't we directly say that a=b (mod n)..??

how do I do this one?

Thanks for any help!

The part I have marked in red is wrong.

Its a nice question...

if n|(a^2 - b^2), n need not necessarily divide a-b but it could divide a+b. Consider n = 5 and a = 4 and b = 1...

In fact n need not divide both a-b and a+b! As an example choose n = 8, a = 3,b=1...

I got until this part:

n divides a^2 - b^2 then we could say for some k, (a-b)(a+b) = nk..now similarly for some l , a+b = nl..

so dividing both of these equations we get: (a-b) = k/l...and I am stuck after this part! is this a right way to proceed??
please help!

well I tried disproving it and got this one. Like you said, just need one example where ti does not work...

For example, a = 7, b = 2, N = 3.

7^2 mod 3 = 1
2^2 mod 3 = 1
so 7^2 mod 3 = 2^2 mod 3

BUT
7 mod 3 = 1
2 mod 3 = 2
so 7 mod 3 != 2 mod 3

So it satisfies our counterexample....but I still don't understand, how do we know that any conditions like this one, proves or disproves? so do we always look for disproving first and pick any examples where it does not work. Or something else?

Didnt you follow my reasoning? Its clear from that...

n|a^2-b^2 = (a-b)(a+b)

Now I realised that if n|(a+b) then n|(a^2 - b^2).... This is how I figured n need not divide a-b.

Now to disprove choose n = a+b for some n,a,b