Last updated at October 28, 2026 by Teachoo
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.