10-26-2009Greatest Common Divisors and Least Common MultiplesRemember the goal of this unit is to build up some of the tools we need for more so-phisticated number systems, like the fractional numbers. In this section we discuss thefollowing two concepts:Definition 1. Let a and b be whole numbers not both 0. The largest number which is adivisor of both a and b is called the greatest common divisor or GCD of a and b. Insymbolic shorthand, the GCD of a and b is written as GCD(a, b).Definition 2. Let a and b. The smallest number which is a multiple of both a and bis called the least common multiple or LCM of a and b. In symbolic shorthand, theLCM of a and b is written as LCM(a, b).• The GCD of 0 and 0 is not defined since every number is a divisor of zero, so therecan’t possibly be a largest one.• Note that for any non-zero whole number a, GCD(0, a) = a since the largest divisorof a is a and 0 is divisible by a.• Note that GCD(a, b) ≤ a and GCD(a, b) ≤ b. (Why?)• Note that LCM(a, b) ≤ a · b. (Why?)Given these definitions, we now must come up with some ways to compute the GCD andLCM of specific numbers.1. Computing the GCD• Method 1: Intersection of Sets.To find GCD(a, b) write out in list notation the set of divisors of a and the setof divisors of b. The intersection of these two sets is the set of common divisorsand the largest number in the intersection is the greatest common divisor. Forexample, if a = 45 and b = 18, then the divisors of 45 gives the setD45= {1, 3, 5, 9, 15, 45}andD18= {1, 2, 3, 6, 9, 18}.The set of common divisors is the setD45∩ D18= {1, 3, 9}and the largest element in this set is 9. So GCD(45, 18) = 9.• Method 2: Prime Factorization Method.To find the GCD of two numbers a and b find the prime power factorizationof a and the prime power factorization of b. The GCD is the largest possibleproduct of prime powers that a and b have in common. For example, if a = 45and b = 18, then we knowa = 32· 51, b = 2 · 32.The only common prime in these factorizations is 3 and the largest power ofthree that appears in both factorizations is 32. So the GCD(45, 18) = 32= 9.If a = 504 and b = 3675, then504 = 23· 32· 71, 3675 = 31· 52· 72and the common primes are 3 and 7. The largest power of 3 which appears inboth is 31. The largest power of 7 that appears in both is 71so the GCD is3 · 7 = 21.2. Computing the LCM• Method 1: Intersection of sets.To find LCM(a, b), we first write out in list notation the set of multiples of aand the set of multiples of b. The intersection of these two sets is the set ofcommon multiples and the smallest number in this intersection is the LCM.For example, if a = 9 and b = 15, thenMa= {9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135, ...}Mb= {15, 30, 45, 60, 75, 90, 105, 120, 135, ...}.ThenM9∩ M15= {45, 90, 135, ...}and the smallest element of this set is clearly 45. So the LCM(9, 15) = 45.• Method 2: Prime Factorization Method.To find LCM(a, b), compute the prime product factorizations of a and b. TheLCM is the product of prime powers in the factorization with the larger expo-nents.For example, if a = 9, b = 15 thena = 32b = 31· 51.The largest power of 3 in these factorizations is 32. The largest power of 5 inthese factorizations is 51so the LCM is 32· 51= 45.If a = 270 and b = 630 thena = 21· 33· 51andb = 21· 32· 51· 7.The largest power of 2 in these factorizations is 21. The largest power of 3 is33. The largest power of 5 is 51. The largest power of 7 is 71. So the primefactorization is 21· 33· 51·
View Full Document
Unlocking...