New version page

TAMU MATH 365 - 365 lect 45

Documents in this Course
Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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,


View Full Document
Download 365 lect 45
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 365 lect 45 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 365 lect 45 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?