Question

1. Let a; b; c; d; n belong to Z with n > 0. Suppose a congruent b (mod n) and c congruent d (mod n). Use the definition

of congruence to

(a) prove that a + c congruent b + d (mod n).

(b) prove that ac congruent bd (mod n).

Expert Answer

Answer 1

Proofs are in the explantion.

Explanation:

We are given the following:

1)
`a \equi b (mod n) \rightarrow a-b=kn` for integer
`k`.

1)
`c \equi  d (mod n) \rightarrow c-d=mn` for integer
`m`.

a)

Proof:

We want to show
`a+c \equiv b+d (mod n)`.

So we have the two equations:

a-b=kn and c-d=mn and we want to show for some integer r that we have

(a+c)-(b+d)=rn. If we do that we would have shown that
`a+c \equiv b+d (mod n)`.

kn+mn = (a-b)+(c-d)

(k+m)n = a-b+ c-d

(k+m)n = (a+c)+(-b-d)

(k+m)n = (a+c)-(b+d)

k+m is is just an integer

So we found integer r such that (a+c)-(b+d)=rn.

Therefore,
`a+c \equiv b+d (mod n)`.

//

b) Proof:

We want to show
`ac \equiv bd (mod n)`.

So we have the two equations:

a-b=kn and c-d=mn and we want to show for some integer r that we have

(ac)-(bd)=tn. If we do that we would have shown that
`ac \equiv bd (mod n)`.

If a-b=kn, then a=b+kn.

If c-d=mn, then c=d+mn.

ac-bd = (b+kn)(d+mn)-bd

= bd+bmn+dkn+kmn^2-bd

= bmn+dkn+kmn^2

= n(bm+dk+kmn)

So the integer t such that (ac)-(bd)=tn is bm+dk+kmn.

Therefore,
`ac \equiv bd (mod n)`.

//