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

Attachment image

1 Answer

  • 1 month ago
    Favorite 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).

Still have questions? Get your answers by asking now.