Last updated at October 28, 2026 by Teachoo
Transcript
Question 2 Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n. An “if and only if” statement requires proving both directions First direction – Suppose d divides m and n, we prove that d divides both n and m mod n Second direction – Suppose d divides m and m mod n, we prove that d divides both m and n Let Remainder = r = m mod n Since m ≥ n, we can write m = qn + r Where r = m mod n And, 0 ≤ r < n Where r = m mod n And, 0 ≤ r < n First direction Suppose 𝒅 divides both 𝑚 and 𝑛. Then there are integers 𝑎,𝑏 such that: 𝒎=𝒂 × 𝒅, 𝒏=𝒃 × 𝒅 Since m=𝑞𝑛+𝑟 Putting 𝑚=𝑎 × 𝑑, 𝑛=𝑏 × 𝑑 𝒂𝒅=𝒒 × 𝒃𝒅+𝒓 𝑟=𝑎𝑑−𝑞𝑏𝑑 𝒓=(𝒂−𝒒𝒃)𝒅 Therefore, 𝒓 is a multiple of 𝒅, So, 𝒅 divides 𝒓 But d already divides 𝑛. Hence it divides both 𝒏 and 𝒓 Reverse direction Suppose 𝑑 divides both 𝑛 and 𝑟. Then: 𝒏=𝒃 × 𝒅, 𝒓=𝒄 × 𝒅 for integers 𝑏,𝑐 Since m=𝑞𝑛+𝑟 Putting 𝑛=𝑏 × 𝑑, 𝑟=𝑐 × 𝑑 𝒎=𝒒 × 𝒃𝒅+𝒓 𝑟=𝑎𝑑−𝑞𝑏𝑑 𝒓=(𝒂−𝒒𝒃)𝒅 𝑚=𝑞 × 𝑏𝑑+𝑐𝑑 𝒎=(𝒒𝒃+𝒄)𝒅 Therefore, 𝒎 is a multiple of 𝒅 So, 𝒅 divides 𝒎 But d already divides 𝑛. Hence it divides both 𝒎 and 𝒏 Since we proved both first and second direction, we can say d divides m and n if and only if d divides both n and m mod n Hence proved