[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.
- 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.
(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).