Math 365 Lecture Notes - © J. Whitfield 10/21/2005 Page 1 of 3 Section 4-5 Math 365 Lecture Notes Section 4.5 – Greatest Common Divisor and Least Common Multiple Definitions/Theorems 1) Greatest Common Divisor of a and b ( ,a b N∈) – 2) Relatively Prime – 3) Least Common Multiple of a and b ( ,a b N∈) – Finding GCD(a,b) 1) Colored Rods Method – The GCD(a, b) is the largest rod that can be used to make one “train” of length a and another “train” of length b. example: Find the GCD(27, 18) 2) Intersection of Sets Method – Find the set of divisors for a and the set of divisors for b. The GCD(a, b) is the largest element in the intersection of these two sets. example: Find the GCD(27, 18) 3) Prime Factorization Method – Find the prime factorization of the given numbers and identify their common prime factors. The GCD is the product of these common factors, each raised to the lowest power of that prime that occurs in the prime factorizations. example: Find GCD(630, 396)Math 365 Lecture Notes - © J. Whitfield 10/21/2005 Page 2 of 3 Section 4-5 4) Euclidean Algorithm – An iterative process that divides the divisor by the remainder until a remainder of zero is obtained. The GCD is the divisor that yields the remainder of zero. example: Find GCD(5850, 3300) Finding LCM 1) Colored Rods Method – Build two “trains”, one with the rod of length a and another with the rod of length b, until the “trains” are the same length. The LCM(a, b) is the “common train” of smallest length. example: Find the LCM(4, 6) 2) Intersection of Sets Method – Let set A be the set of multiples of a and set B be the set of multiples of b. The LCM(a, b) is the smallest element in A B∩. example: Find the LCM(12, 8). 3) Prime Factorization Method – Find the prime factorization of the given numbers. Take each of the primes that are factors of any of the given numbers. The LCM is the product of these primes, each raised to the greatest power of the prime that occurs in the prime factorizations. example: Find LCM(630, 396)Math 365 Lecture Notes - © J. Whitfield 10/21/2005 Page 3 of 3 Section 4-5 4) Division by Primes Method – An iterative process that requires dividing given numbers by primes until a row of all ones is reached. The LCM is the product of the prime divisors. example: Find LCM(120, 72, 12) Relating LCM(a,b) to GCD(a,b) Theorem 4 – 8: For all ,a b N∈, GCD(a, b) LCM(a, b) = a b. example: If GCD(a, b) = 30 and the product of a and b is 189000, what is LCM(a,