Finding the Greatest Common Divisor - Methods & Solved Problems - Greatest Common Divisor as an Algorithm

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

part 3 - Finding the Greatest Common Divisor - 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

Finding the Greatest Common Divisor After finding both divisor lists, we must identify the entries common to them. The procedure is: Start with an empty common-divisors list. Examine each entry in the first divisor list. Check whether it appears in the second list. If it does, append it to common-divisors. Example – find gcd (325, 825) Now, divisors(325) =[1, 3, 5, 15, 25, 75, 125, 375] divisors(825) =[1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825] Then, we compare The completed list is: [1, 3, 5, 15, 25, 75] Because it is increasing, its rightmost entry is greatest. Thus, gcd(375, 825) = 75 divisors(325) | Is it present in divisors(825)? | Common-divisor list 1 | Yes | [1] 3 | Yes | [1, 3] 5 | Yes | [1, 3, 5] 15 | Yes | [1, 3, 5, 15] 25 | Yes | [1, 3, 5, 15, 25] 75 | Yes | [1, 3, 5, 15, 25, 75] 125 | No | Unchanged 375 | No | Unchanged gcd(375, 825) = 75 Why can the common-divisor list never be empty? Since 1 divides all numbers Therefore, 1 must divide both numbers So, common-divisor list will always have 1 Now, we can write our algorithm

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.