# congruence and the Division Algorithm...

• Jul 8th 2008, 09:08 AM
Vedicmaths
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!
• Jul 8th 2008, 09:28 AM
ThePerfectHacker
Quote:

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!

$1^2 \equiv (-1)^2 (\bmod 3)$.
• Jul 8th 2008, 09:31 AM
Isomorphism
Quote:

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...
• Jul 8th 2008, 02:20 PM
Vedicmaths
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??
• Jul 8th 2008, 02:41 PM
Vedicmaths
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?
• Jul 8th 2008, 08:56 PM
Isomorphism
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 :)