Division Algorithm Discussion

(The following is/are the initial prompt(s) for an online discussion; students may have posted responses, and prompts for further discussion may have been added, but these things are not shown.)

The division algorithm (section 3.5 in our textbook) is what justifies thinking of modular congruence in terms of remainders, i.e., thinking of a statement such as “a ≡ b (mod n)” as meaning that a and b have the same remainder when divided by n. The richer understanding of modular congruence introduced by the division algorithm also leads to a number of properties that are useful for reasoning about modular congruences. This discussion basically asks you (collectively) to do the textbook’s progress check 3.30, which asks you to prove one of those useful properties.

Discuss ideas you have for proving that if a, b, c, and d are integers, and n a natural number, such that a ≡ b (mod n) and c ≡ d (mod n), then (a+c) ≡ (b+d) (mod n). For example, what definitions might you use to start such a proof? What would you do with those definitions? Can you adapt ideas from other proofs in the book to this one? If so, which ideas? Eventually, can you put the ideas that others have offered together into a complete proof?