Slide 1Chapter 5: Number TheorySlide 3Greatest Common Factor and Least Common MultipleGreatest Common FactorFinding the Greatest Common Factor (Prime Factors Method)Example: Greatest Common FactorFinding the Greatest Common Factor (Dividing by Prime Factors Method)Slide 9Finding the Greatest Common Factor (Euclidean Algorithm)Example: Euclidean AlgorithmLeast Common MultipleFinding the Least Common Multiple (Prime Factors Method)Example: Finding the LCMFinding the Least Common Multiple (Dividing by Prime Factors Method)Slide 16Slide 17Finding the Least Common Multiple (Formula)Example: LCM FormulaChapter 5Number Theory © 2008 Pearson Addison-Wesley.All rights reserved© 2008 Pearson Addison-Wesley. All rights reserved5-3-2Chapter 5: Number Theory5.1 Prime and Composite Numbers 5.2 Selected Topics From Number Theory5.3 Greatest Common Factor and Least Common Multiple 5.4 The Fibonacci Sequence and the Golden Ratio© 2008 Pearson Addison-Wesley. All rights reserved5-3-3Chapter 1Section 5-3Greatest Common Factor and Least Common Multiple© 2008 Pearson Addison-Wesley. All rights reserved5-3-4Greatest Common Factor and Least Common Multiple•Greatest Common Factor•Least Common Multiple© 2008 Pearson Addison-Wesley. All rights reserved5-3-5Greatest Common FactorThe greatest common factor (GCF) of a group of natural numbers is the largest number that is a factor of all of the numbers in the group.© 2008 Pearson Addison-Wesley. All rights reserved5-3-6Finding the Greatest Common Factor (Prime Factors Method)Step 1 Write the prime factorization of each number.Step 2 Choose all primes common to all factorizations, with each prime raised to the least exponent that appears.Step 3 Form the product of all the numbers in Step 2; this product is the greatest common factor.© 2008 Pearson Addison-Wesley. All rights reserved5-3-7Example: Greatest Common FactorFind the greatest common factor of 360 and 1350.3 23 2360 2 3 51350 2 3 5= � �= � �SolutionThe prime factorization is below.The GCF is 2 · 32 · 5 = 90.© 2008 Pearson Addison-Wesley. All rights reserved5-3-8Finding the Greatest Common Factor (Dividing by Prime Factors Method)Step 1 Write the numbers in a row.Step 2 Divide each of the numbers by a common prime factor. Try 2, then 3, and so on.Step 3 Divide the quotients by a common prime factor. Continue until no prime will divide into all the quotients. Step 4 The product of the primes in steps 2 and 3 is the greatest common factor.© 2008 Pearson Addison-Wesley. All rights reserved5-3-9Finding the Greatest Common Factor (Dividing by Prime Factors Method)Find the greatest common factor of 12, 18, and 30.Solution2 12 18 30 6 9 15 2 3 10Divide by 2Divide by 3Since there are no common factors in the last row the GCF is 2 · 3 = 6.No common factors3© 2008 Pearson Addison-Wesley. All rights reserved5-3-10Finding the Greatest Common Factor (Euclidean Algorithm)To find the greatest common factor of two unequal numbers, divide the larger by the smaller. Note the remainder, and divide the previous divisor by this remainder. Continue the process until a remainder of 0 is obtained. The greatest common factor is the last positive remainder in this process.© 2008 Pearson Addison-Wesley. All rights reserved5-3-11Example: Euclidean AlgorithmUse the Euclidean algorithm to find the greatest common factor of 60 and 168.260 168120 48148 604812412 4848 0SolutionStep 1 Step 2 Step 3The GCF is 12.© 2008 Pearson Addison-Wesley. All rights reserved5-3-12Least Common MultipleThe least common multiple (LCM) of a group of natural numbers is the smallest natural number that is a multiple of all of the numbers in the group.© 2008 Pearson Addison-Wesley. All rights reserved5-3-13Finding the Least Common Multiple (Prime Factors Method)Step 1 Write the prime factors of each number.Step 2 Choose all primes belonging to any factorization; with each prime raised to the largest exponent that appears.Step 3 Form the product of all the numbers in Step 2; this product is the least common multiple.© 2008 Pearson Addison-Wesley. All rights reserved5-3-14Example: Finding the LCMFind the least common multiple of 360 and 1350.3 23 2360 2 3 51350 2 3 5= � �= � �SolutionThe prime factorization is below.The LCM is 23 · 33 · 52 = 5400.© 2008 Pearson Addison-Wesley. All rights reserved5-3-15Finding the Least Common Multiple (Dividing by Prime Factors Method)Step 1 Write the numbers in a row.Step 2 Divide each of the numbers by a common prime factor. Try 2, then 3, and so on.Step 3 Divide the quotients by a common prime factor. When no prime will divide all quotients, but a prime will divide some of them, divide where possible and bring any nondivisible quotients down. Continued on next slide…© 2008 Pearson Addison-Wesley. All rights reserved5-3-16Finding the Least Common Multiple (Dividing by Prime Factors Method)Step 3 (step 3 continued) Continue until no prime will divide any two quotients. Step 4 The product of the prime divisors in steps 2 and 3 as well as all remaining quotients is the least common multiple.© 2008 Pearson Addison-Wesley. All rights reserved5-3-17Finding the Least Common Multiple (Dividing by Prime Factors Method)Find the least common multiple of 12, 18, and 30.Solution2 12 18 30 6 9 15 2 3 5Divide by 2Divide by 3The LCM is 2 · 3 · 2 · 3 · 5 = 180No common factors3© 2008 Pearson Addison-Wesley. All rights reserved5-3-18Finding the Least Common Multiple (Formula)LCM .greatest common factor of and m nm n�=The least common multiple of m and n is given by© 2008 Pearson Addison-Wesley. All rights reserved5-3-19Example: LCM Formula360 1350 486000LCM 540090 90�= = =Find the LCM of 360 and 1350.SolutionThe GCF is