Ex 11.2, 3 (ii) - If we list out divisors - Chapter 11 Class 9 Ganita - Exercise Set 11.2

part 2 - Ex 11.2, 3 (ii) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Ex 11.2, 3 (ii) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Ex 11.2, 3 (ii) - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo ยท Class 9 Explore Class 9

Transcript

Ex 11.2, 3 (ii) Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6). (ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described? Not necessarily. Its final step depends on the list being in increasing order For 18, appending divisors pair by pair gives [1, 18, 2, 9, 3, 6] This list is not increasing For 36, pairwise listing gives: [๐Ÿ,๐Ÿ‘๐Ÿ”,๐Ÿ,๐Ÿ๐Ÿ–,๐Ÿ‘,๐Ÿ๐Ÿ,๐Ÿ’,๐Ÿ—,๐Ÿ”] Applying the original GCD algorithm to 18 and 36 Every divisor of 18 appears in the list for 36, so the common-divisor list becomes: [๐Ÿ, ๐Ÿ๐Ÿ–, ๐Ÿ, ๐Ÿ—, ๐Ÿ‘ ,๐Ÿ”] The original final step says: Report the rightmost entry. That would report 6 , which is wrong: gcd(18,36)=18 What exactly went wrong? Finding the divisors in pairs was correct. Identifying the common divisors was also correct. The failure occurred because "rightmost" no longer meant "greatest.โ€ Two ways to fix it asd Applying the original GCD algorithm to 18 and 36 Every divisor of 18 appears in the list for 36, so the common-divisor list becomes: [๐Ÿ, ๐Ÿ๐Ÿ–, ๐Ÿ, ๐Ÿ—, ๐Ÿ‘ ,๐Ÿ”] The original final step says: Report the rightmost entry. That would report 6 , which is wrong: gcd(18,36)=18 What exactly went wrong? Finding the divisors in pairs was correct. Identifying the common divisors was also correct. The failure occurred because "rightmost" no longer meant "greatest.โ€ Two ways to fix it asd The failure occurred because "rightmost" no longer meant "greatest.โ€ Two ways to fix it For the second method: Set greatest to the first common divisor. Examine each remaining common divisor. If it is greater than greatest, update greatest. Report greatest. For: [1,18,2,9,3,6], the stored value changes from 1 to 18, then remains 18. Pairwise listing works after we correct how the greatest entry is selected. Modification | Why it works Sort the common-divisor list into increasing order, then choose its rightmost entry. | Restores the ordering needed by the original final step. Examine the common-divisor list and explicitly select its greatest entry. | Finds the maximum regardless of list order. For: [1, 18, 2, 9, 3, 6], the stored value changes from 1 to 18, then remains 18. Thus, Pairwise listing works after we correct how the greatest entry is selected.

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.