|
Lesson 33 GREATEST COMMON DIVISOR
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |  |
We will now learn how to find the greatest common divisor and the lowest common multiple of two numbers from their prime factorizations. (In Lesson 23 we saw how to find the LCM directly.) But first, let us see how to find all the divisors of a number from its prime factors.
We say that one number is a divisor of a second when the second is its multiple. 4 is a divisor of 36 because 36 is a multiple of 4: 36 = 9 × 4. And we can see that in the prime factors of 36:
36 = 2 × 2 × 3 × 3.
Apart from the order, 36 = 9 × 4.
4 is a divisor of 36. (And so is 9.)
All the divisors of a number can be found from its prime factors.
Example 1. Here is the prime factorization of 60:
60 = 2 × 2 × 3 × 5.
By taking those primes singly, then two at a time, then three at a time, and so on, we can construct all the divisors of 60.
Singly: 2, 3, 5, and 1.
Do not forget 1. Although 1 is not a prime, 1 is a divisor of every number.
Two at a time: 2 × 2, 2 × 3, 2 × 5, 3 × 5.
That is: 4, 6, 10, 15.
Three at a time: 2 × 2 × 3, 2 × 2 × 5, 2 × 3 × 5.
That is: 12, 20, 30.
All four: 2 × 2 × 3 × 5 = 60.
These are all the divisors of 60. 60 is a multiple of each one.
Problem 1. Write the prime factorization of 180. Then construct all its divisors.
To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").
Do the problem yourself first!
180 = 2 × 2 × 3 × 3 × 5.
Singly: 2, 3, 5, and 1.
Two at a time: 2 × 2, 2 × 3, 2 × 5, 3 × 3, 3 × 5.
Three at a time: 2 × 2 × 3, 2 × 2 × 5, 2 × 3 × 3, 2 × 3 × 5,
3 × 3 × 5.
Four at a time: 2 × 2 × 3 × 3, 2 × 2 × 3 × 5, 2 × 3 × 3 × 5.
All five: 2 × 2 × 3 × 3 × 5
These numbers are:
1 2 3 5 4 6 10 9 15 12 20 18 30 45 36 60 90 180
Problem 2. A certain number is not divisible by 3. Therefore why is it not divisible by 12?
Since 12 = 2 × 2 × 3, then any number divisible by 12 -- that is, which is a multiple of 12 -- must have 3 as a prime divisor.
Here are all the divisors of 12:
Here are all the divisors of 20:
Which numbers are the common divisors of 12 and 20?
What number is their greatest common divisor?
Problem 3. What number is the greatest common divisor of each pair?
| a) | 6, 9. 3 | b) | 8, 12. 4 | c) | 16, 40. 8 | ||
| d) | 7, 14. 7 | e) | 4, 20. 4 | f) | 6, 42. 6 | ||
| g) | 5, 11. 1 | h) | 6, 35. 1 | i) | 1, 12. 1 | ||
Problem 4. Which prime factors do these two numbers share?
2 × 5 is their greatest common divisor.
Problem 5. Find the greatest common divisor of each pair.
| a) | 3 × 11 and 11 × 13. 11 | b) | 5 × 7 × 7 and 5 × 5 × 7. 5 × 7 |
c) 2 × 3 × 7 and 5 × 7 × 7 × 11. 7
d) 2 × 2 × 2 × 3 × 5 × 5 and 2 × 3 × 3 × 5 × 5 × 5 × 7.
They share one 2, one 3, and two 5's.
e) Those numbers don't share any primes. But 1 is a common divisor of
e) every pair of numbers. In the case, it is their only -- and greatest --
e) common divisor.
f) 5 × 5 and 5 × 5 × 5 × 5 × 5. 5 × 5
Problem 6. Find the greatest common divisor of each pair.
| a) | 45 and 75. 15 | b) | 42 and 63. 21 | c) | 30 and 77. 1 |
a) What is the greatest common divisor of 12 and 35? 1
b) Write the prime factorizations of 12 and 35.
c) What prime factors do they share? None.
That is how to recognize when two numbers are relatively prime.
Problem 8. Which of these pairs are relatively prime?
| a) | 6 and 35. Yes. | b) | 6 and 21. No. | c) | 8 and 27. Yes. | ||
| d) | 13 and 91. No. | e) | 9 and 20. Yes. | f) | 1 and 16. Yes. | ||
We saw examples of what we mean by the lowest common multiple in Lesson 23. We also saw a way to find it.
Problem 9. What number is the lowest common multiple of each pair?
| a) | 9 and 12. 36 | b) | 6 and 8. 24 | c) | 10 and 12. 60 | ||
| d) | 3 and 15. 15 | e) | 4 and 24. 24 | f) | 11 and 55. 55. | ||
| g) | 2 and 3. 6 | h) | 5 and 8. 40 | i) | 8 and 9. 72 | ||
Problem 10. Name the lowest common multiple (LCM) of each pair. Then name their greatest common divisor (GCD).
a) 12 and 16. LCM = 48. GCD = 4.
b) 15 and 20. LCM = 60. GCD = 5.
c) 13 and 39. LCM = 39. GCD = 13.
d) 5 and 8. LCM = 40. GCD = 1.
e) 20 and 24. LCM = 120. GCD = 4.
Problem 11. What number is the lowest common multiple of 6, 8, and 10? 120
We will now see how to find the LCM by writing the prime factorizations.
Example 2. Here are the prime factorizations of 24 and 20.
24 = 2 × 2 × 2 × 3. 20 = 2 × 2 × 5.
To evaluate that number, the order of the factors does not matter. (Lesson 9.) Therefore let us take advantage of 2 × 5 = 10. We will group the factors as follows:
(2 × 5) × (2 × 2 × 3) = 10 × 12 = 120.
Problem 12. Construct the lowest common multiple of the following.
a) 2 × 3 and 3 × 5. LCM = 2 × 3 × 5 = 30.
b) 3 × 3 × 5 and 3 × 5 × 5. LCM = 3 × 3 × 5 × 5 = 225.
c) 2 × 3 × 5 × 5. and 2 × 2 × 2 × 5 × 7.
c) LCM = 2 × 2 × 2 × 3 × 5 × 5 × 7 = 4200.
d) 2 × 2 and 2 × 2 × 2. LCM = 2 × 2 × 2 = 8.
e) 7 and 11. LCM = 7 × 11 = 77.
f) 2 × 3 and 5 × 7. LCM = 2 × 3 × 5 × 7 = 210.
g) 2 × 5, 7 × 11, and 5 × 11. LCM = 2 × 5 × 7 × 11 = 770.
Problem 13. Find the lowest common multiple of each pair.
a) 21 and 33. 3 × 7 × 11 = 231.
| b) | 65 and 39. 195 | c) | 54 and 75. 1350 | ||||||||||||||||||||||||||||||||||||||||||||||||||||
| d) | 6 and 77. 462 | e) | 17 and 33. 561 | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Problem 14. Find the lowest common multiple of
a) 6, 8, and 10. 2 × 2 × 2 × 3 × 5 = 120. Compare Problem 11.
b) 14, 35, and 55. 770.
Problem 15. 15 and which other numbers have 60 as their lowest common multiple?
60 = 2 × 2 × 3 × 5. Since 15 = 3 × 5, then each of the other numbers must have 2 × 2. Those numbers are:
2 × 2 = 4.
2 × 2 × 3 = 12.
2 × 2 × 5 = 20.
2 × 2 × 3 × 5 = 60.
Introduction | Home | Table of Contents
Please make a donation to keep TheMathPage online.
Even $1 will help.
