Question 2 - Assume that m ≥ n. Verify that d divides m and n if - End-of-Chapter Exercises

part 2 - Question 2 - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Question 2 - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Question 2 - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo · Class 9 Explore Class 9

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

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.