5 Let ab e Z Let m e Z 0 We say a is congruent to b mod m i

5. Let a,b e Z. Let m e Z > 0. We say a is congruent to b mod m iff m|(a - b). If a is congruent to b mod m, we write ab(mod m). Prove that if a b (mod m) and c d(mod m), then (a+c) (b+d)(mod m) and ac bd (mod m)

Solution

From a = b(mod m), we get that : a - b = P*m

Similarly, c - d = Q*m

Adding :

a - b + c - d = Pm + Qm

a + c = b + d + Pm + Qm

a + c = b + d + m(P + Q)

Pm + Qm is a multiple of \'m\'....
This indicates that when (a + c) is divided by m, we get the remainder as (b + d)

Therefore,
a + c = (b + d)(mod m)

Hence proved!

----------------------------------------------------
a - b = P*m
a = b + Pm

c - d = Q*m
c = d + Qm

Multiply them out :

ac = (b + Pm)(d + Qm)

ac = bd + Qmb + Pmd + PQm^2

ac = bd + m(Qb + Pd + PQm)

m(Qb + Pd + PQm) is something that is divisible by m.....

Therefore, the bd on the right is simply the remainder when ac is divided by m...

And thus, we get :

ac = bd(mod m) ---> ANSWER

Hence both of them have been proved!