Exercise 2: Proving Common Divisors of 84 & 36 Are Common Divisors of 36 & 12 — Possible Solution ==================================================================== GIVEN ------------------------------ a = 84, b = 36. First, apply the division algorithm (Chapter 2): 84 = 36*2 + 12, so q = 2, r = 12 = 84 mod 36. THE PROOF, USING CHAPTER 2'S OWN PROPERTIES DIRECTLY ------------------------------ Let d be ANY common divisor of 84 and 36 - that is, d | 84 and d | 36. Since d | 36, Chapter 2's own "multiple" property (if a | b, then a | bc for any integer c) says directly that d | (36 * 2), which is d | 72. Since d | 84 and d | 72, Chapter 2's own "subtraction" property (if a | b and a | c, then a | (b - c)) says directly that d | (84 - 72), which is d | 12. So: d | 36 (already given) and d | 12 (just shown) - meaning d is also a common divisor of 36 and 12. RESULT ------------------------------ Every common divisor of 84 and 36 is also a common divisor of 36 and 12 (= 84 mod 36) - shown directly from the two named divisibility properties, without ever listing out or checking individual candidate divisors. (As a separate confirmation, not part of the proof: the actual common divisors of (84,36) are {1,2,3,4,6,12}, and the actual common divisors of (36,12) are also {1,2,3,4,6,12} - identical sets, matching what the proof predicts.) WHY THIS WORKS AS AN ANSWER ------------------------------ The proof follows this chapter's own template exactly - starting from an arbitrary common divisor d, then applying the multiple property and the subtraction property in sequence to derive d | 12 - rather than shortcutting to the answer by simply listing divisors, which is explicitly what the exercise asked to avoid.