# Thread: Division Algorithm...

1. ## Division Algorithm...

I need some help in division algorithm...

Q1) prove that a+c is in equivalence relation with b+d (mod n)
(i.e.) a+c=b+d(mod n)

Q2) prove that ac=bd(mod n)..

2. I got a little but of idea for the second one...
if a = b(mod n) and c = d(mod n), then ac = bd(mod n).

So, by using the definition of the modulus:

a = b + nk and c = d + nl for some integers we'll call k and l.

So by multiplying both of these conditions we then get:-

ac = (b + nk)(d + nl)
= bd + nkd + nlb + n^2kl
= bd + n(kd + lb + nkl)

which means that ac = bd(mod n) since (kd + lb + nkl) is just some
integer.

I hope this is right!

I did the similar operation for 1st but I am still not sure on how to resolve it?
coz I keep getting the some random terms in there...

Thanks for the any help!

3. Originally Posted by Vedicmaths
I got a little but of idea for the second one...
if a = b(mod n) and c = d(mod n), then ac = bd(mod n).

So, by using the definition of the modulus:

a = b + nk and c = d + nl for some integers we'll call k and l.

So by multiplying both of these conditions we then get:-

ac = (b + nk)(d + nl)
= bd + nkd + nlb + n^2kl
= bd + n(kd + lb + nkl)

which means that ac = bd(mod n) since (kd + lb + nkl) is just some
integer.

I hope this is right!
Yes thats right...

I did the similar operation for 1st but I am still not sure on how to resolve it?
coz I keep getting the some random terms in there...

Thanks for the any help!
Use the same thing for the first:

"a = b + nk and c = d + nl for some integers we'll call k and l"

a+c = b+d + n(k+l)

"which means that a+c = b+d(mod n) since (k + l) is just some
integer."