Greatest Common Divisor as an Algorithm - Explanation Class 9 - Greatest Common Divisor as an Algorithm

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

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

part 4 - 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

Greatest Common Divisor Let’s first look at what is Greatest Common Divisor (gcd) Greatest Common Divisor (GCD) The biggest number that divides both numbers exactly. Also called HCF — Highest Common Factor. A real-life problem Make the greatest possible number of identical snack bags. Use everything, with nothing left over. j999 $999 om 3999 ao 12 juice cartons 18 biscuit packets Each bag: 2 juice cartons + 3 biscuit packets 12+6=2 18+6=3 The maximum number of bags is GCD(12, 18) = 6. What does GCD mean? 6 identical bags Divisor: divides a number with no remainder. Common: divides BOTH numbers. Greatest: the largest of those common divisors. 6 divides both 12 and 18 exactly. Calculate it by listing factors egeeiia 1. 2,3 4 ©, 4, 12 Choose the largest Factors of 18: 1, 2, 3, ©) 9, 18 Gea se a) Common factors: 1, 2, 3, 6 shared factor. Greatest common factor = 6 4) A faster method: Euclid’s algorithm :) 18 = 12x1+6 Divide 18 by 12 > remainder 6. 12=6x2+0 Divide 12 by 6 > remainder 0. Stop at remainder 0. The last divisor is the GCD: 6. Replace (larger, smaller) with (smaller, remainder). Repeat until the remainder is 0. (18, 12) > (12,6) > (6, 0) GCD(12, 18) = 6 6 is the largest number that divides BOTH exactly. A divisor, also called a factor, divides a number exactly, leaving no remainder. For example: (18)/(3)=6 Therefore, 3 is a divisor of 18 . But: (18)/(4)=4(2)/(4) Since there is a remainder, so 4 is not a divisor of 18 . A common divisor divides both numbers. The greatest common divisor, or GCD, is the greatest of their common divisors. GCD and HCF (Highest Common Factor) mean the same thing. For example: Divisors of 12 = 1, 2, 3, 4, 6, 12 Divisors of 18 = 1, 2, 3, 6, 9, 18 Thus, Greatest common Divisor (gcd) = 6 In this section, we make an algorithm for finding gcd of two numbers We use the definition of gcd to make an algorithm Using definition to make an algorithm for gcd Break the problem into smaller tasks: Find the divisors of the first number Find the divisors of the second number Find the numbers present in both collections Select the greatest This is problem decomposition: breaking a problem into smaller, manageable parts. Now, to make an algorithm for gcd, we first need to make an Algorithm to find Divisors of a Number Find the divisors of the second number Find the numbers present in both collections Select the greatest This is problem decomposition: breaking a problem into smaller, manageable parts. Now, to make an algorithm for gcd, we first need to make an Algorithm to find Divisors of a Number

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.