# [Discrete Math] stuck in Proof by Contradiction involving modular arithmetic?

I need to prove the following through a proof of contradiction.

(a ≡ b(mod m) ∧ c ≡ d(mod m)) → a + c ≡ b + d(mod m)

I attached a picture of what I have so far. I'm unsure of what to do next but I was thinking maybe algebra? But nothing I've tried has worked so far. Please help.

### 1 Answer

- DerealizationLv 51 month agoFavorite Answer
Assume to the contrary that a ≡ b (mod m) and c ≡ d (mod m) but we have that (a + c) ≢ (b + d) (mod m).

This implies that

(a + c) - (b + d) = mk + r

where r is a remainder.

Note though

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

But since a ≡ b (mod m), we have

(a - b) = ms, where s is an integer

Likewise, since c ≡ d (mod m), we have

(c - d) = mt for some integer t.

Thus, we may write

ms + mt = mk + r

===> r = ms + mt - mk = m(s + t - k)

This implies though that m evenly divides (a + c) - (b + d), but this contradicts our assumption that (a + c) ≢ (b + d) (mod m).