First Algorithm for gcd - Full steps with Examples - Class 9 Maths - Greatest Common Divisor as an Algorithm

part 2 - First Algorithm for gcd - Greatest Common Divisor as an Algorithm - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo ยท Class 9 Explore Class 9

Transcript

First Algorithm for gcd Combining divisor-finding and list-comparison gives the complete algorithm Algorithm to find gcd(m,n) Algorithm to find gcd(m, n) 1. Let divisors-of-m be the list obtained by computing divisors(m) Let divisors-of-n be the list obtained by computing divisors(n) Start with an empty List common-divisors The World of Algorithms 43 . For each number x in the List of divisors-of-m - If x also appears in the List of divisors-of-n, add x to the List common-divisors . Report the rightmost element of the list common- divisors as gcd(m,n) An important new idea: reuse an existing algorithm We have already written a procedure for finding divisors. We use it twice rather than describe all its steps again. divisors(๐‘š) and divisors(๐‘›) mean "apply the divisor-finding algorithm to these inputs." Why is the complete algorithm correct? The first two steps find every divisor of each input. The comparison step retains exactly the common divisors. Their increasing order is preserved. The last entry is therefore the greatest common divisor. The final step depends on ordering. Choosing the rightmost entry works because the list is increasing-not simply because it is a list.

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.