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