28 Primes and Greatest Common Factor
[LA math standards will be here.]
Factors and Prime Numbers
In these first few acitivities, you’ll be using C-strips to explore divisors, factors, prime numbers and composite numbers.
Take out the Hot Pink (H) C-strip, which has a length 12. Use your C-strips (one color at a time) to see if you can form a train made up of C-strips of the same color equal in length to the hot pink C-strip. In other words, see if you can do it with all whites (always possible for any train length), or all reds, or all light greens, etc. You should be able to make six different trains each train is made up of a single color. Draw a picture of each of these trains under the Hot Pink one shown. I’ve drawn two trains for you already one is simply the hot pink strip (a train consisting of just one C-strip), and a second is made up of three purple C-strips.
Train 1 illustrates the multiplication [latex]1 \times[/latex]H [latex]=[/latex] H, or [latex]1\times12=12[/latex].
Train 2 illustrates the multiplication [latex]3 \times[/latex] P [latex]=[/latex] H, or [latex]3 \times 4 = 12[/latex].
Train 3 illustrates the multiplication [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = H, or [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = [latex]12[/latex].
Train 4 illustrates the multiplication [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = H, or [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = [latex]\underline{\qquad}[/latex]
Train 5 illustrates the multiplication [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = H, or[latex]\underline{\qquad}\times\underline{\qquad}[/latex] = [latex]\underline{\qquad}[/latex]
Train 6 illustrates the multiplication [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = H, or [latex]\underline{\qquad}\times\underline{\qquad}[/latex] = [latex]\underline{\qquad}[/latex]
The set of numbers placed in the blanks above before the equal sign in the equations with numbers are called factors or divisors of 12. Note, that because of the commutative property of multiplication, each factor or divisor was listed twice representing different one-color trains. Without considering the meanings of the numbers for C-strips, we can list all the factors of 12 as below from the least to the greatest:
[latex]1, 2, 3, 4, 6, 12[/latex]
Use the same procedure used in Activity 1 to make all possible trains for each of the given lengths. Then, after discovering the possible trains that can be made, list the factors (the actual numbers) of each number from the least to the greatest. Every number greater than 1 has at least two factors.
a. Make one-color trains with a length 2.
List all the factors of 2 : [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
b. Make one-color trains with a length 3.
List all the factors of 3: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
c. Make one-color trains with a length 4.
List all the factors of 4: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
d. Make one-color trains with a length 5.
List all the factors of 5: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
e. Make one-color trains with a length 6.
List all the factors of 6: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
f. Make one-color trains with a length 7.
List all the factors of 7: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
g. Make one-color trains with a length 8.
List all the factors of 8: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
h. Make one-color trains with a length 9.
List all the factors of 9: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
i. Make one-color trains with a length 10.
List all the factors of 10: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
j. Make one-color trains with a length 11.
List all the factors of 11: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
k. Make one-color trains with a length 13.
List all the factors of 13: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
l. Make one-color trains with a length 14.
List all the factors of 14: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
m. Make one-color trains with a length 15.
List all the factors of 15: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
n. Make one-color trains with a length 16.
List all the factors of 16: [latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
Observe the results in Activity 2 and answer the following.
a. List the numbers in Activity 2 that have exactly 2 factors:
[latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
b. What do you notice about the 2 factors each of these number have? Is there a pattern or anything they have in common with each other?
c. List numbers from Activity 2 that have an odd number (3 or 5) of factors:
[latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
d. What do all of these numbers have in common?
[latex]\underline{\qquad\qquad\qquad\qquad\qquad\qquad}[/latex]
Definition – Prime Number and Composite Number
A whole number that has exactly two different factors is called a prime number.
Any whole number larger than 1 that is not prime is called a composite number.
Any whole number larger than 1 that is not prime is called a composite number. A whole number that has exactly two different factors is called a prime number. That is, if a number is prime, its only factors are 1 and itself. In other words, if a number, p, is prime, its only factors are 1 and p. If you are using the C-strips and try to make a rectangle out of a train that has a length that is a prime number, the only possibility is when the width is 1 and the length is the length of the original train. That is because those are the only factors, and no other number divides into it.
Below is the list of all prime numbers less than 16 that we have found in Activity 3 above:
[latex]2, 3, 5, 7, 11, 13[/latex]
NOTE:
- 0 is neither prime nor composite.
- 1 is NOT prime since it doesn’t have two different factors it only has one 1, so 1 is neither prime nor composite. Any whole number larger than 1 is either prime or composite.
- 2 is the only even prime number.
If a number is composite, it means that it has more than 2 factors, and can be written as a product of factors less than itself. For instance, 12 is not a prime number. It can be written as [latex]2\cdot6[/latex] or [latex]3\cdot4[/latex]. This is called factoring, and [latex]2\cdot6[/latex] and [latex]3\cdot 4[/latex] are two ways of factoring 12, or factorization.
Factorizing Numbers
What we are going to do in this section is to factor composite numbers. Any composite number can be factored as a product of two numbers smaller than it. But here the ultimate goal is to factor the number into a product of primes; that is, no one of them can be factored further. We call this process prime factoring. For instance, we’ve factored 12 as [latex]2\cdot6[/latex] and [latex]3\cdot 4[/latex], but both still have a composite factor respectively, 6 and 4, to allow a further step of factoring:
[latex]12=2\cdot6=2\cdot2\cdot3[/latex], or [latex]12=3\cdot4=3\cdot2\cdot2[/latex].
At this point, the composite number is factored as the product of three prime factors. In general, we break down a composite number to two factors, then keep breaking down each until all factors are prime. Example 1 shows the process of prime factoring the number 210.
Example 1
Prime factor 210 by breaking it to two factors first then , and show the individual steps.
Solution 1:
[latex]210 = 21\cdot10 = 3\cdot 7\cdot 2\cdot5[/latex]
Solution 2:
[latex]210 = 3\cdot70 = 2 \cdot105 = 2\cdot3 \cdot 35 = 2 \cdot 3 \cdot 5 \cdot 7[/latex]
Solution 3:
[latex]210 = 30 \cdot 7 = 5 \cdot 6 \cdot 7 = 5 \cdot 2 \cdot 3 \cdot 7[/latex]
Similar to the prime factoring of 12, there are many other ways one might go about factoring 210, but in the end, there are 4 prime factors that when multiplied together equal 210. Because of the commutative and associative properties of multiplication, [latex]3 \cdot 7 \cdot 2 \cdot 5 = 2 \cdot 3 \cdot 5 \cdot 7 = 5 \cdot 2 \cdot 3 \cdot 7[/latex]. Usually, the primes are written in ascending order (from the smallest factor to the largest factor. We write that the prime factorization of 210 is [latex]2 \cdot 3 \cdot 5 \cdot 7[/latex].
This leads to a very important theorem. You can think of the prime numbers as building blocks for all whole numbers greater than 1 under the operation of multiplication. Every whole number greater than 1 is either prime, or can be expressed as the product of prime factors (called the prime factorization). The fact that any composite number can be written as a unique product of primes is so important that it is called the Fundamental Theorem of Arithmetic.
Key Takeaway – The Fundamental Theorem of Arithmetic
Every composite number has exactly one unique prime factorization (except for the order in which the factors are written.)
Note again that the order in which the factors are written doesn’t matter, which is guaranteed by the commutative and associative properties of multiplication. However, for consistency, they are usually written in ascending order (from least to greatest). Also, exponents may be used if a factor is repeated in the prime factorization. For instance, the prime factorization of 12 is usually written as [latex]2 \cdot 2 \cdot 3[/latex] or [latex]2^{2} \cdot 3[/latex].
For the given composite number, follow the procedure of Example 1 to write it as a product of two factors first, then keep factoring each until all factors are prime. Write the prime factorization so the factors are written in ascending order (from smallest to largest). Show each of the individual steps one at a time, not just the final product.
a. 45
Solution
b. 65
Solution
c. 200
Solution
d. 91
Solution
e. 76
Solution
f. 350
Solution
g. 189
Solution
h. 74
Solution
i. 512
Solution
j. 147
Solution
There are other methods commonly used to find the prime factorization. One is called a FACTOR TREE, which presents the breaking down process as a tree-shape: The number you are trying to factor is like the “root” of the tree, but is placed at the top; so, it’s actually an upside down tree. Then we draw two “branches” down to the two factors we get in the first breaking down. If a number at a branch is not prime, we draw two branches down from that number and factor it as the product of any two factors. At the end of each branch is a smaller factor, which is like “a leaf”. If a leaf is prime, circle it, and it is one of the factors in the prime factorization of the number. Otherwise, branch off again. When all of the leaves are circled prime numbers, you are done. The prime factorization of the root is the product of the prime leaves.
Example 2
Use a factor tree to show the prime factoring of 12, [latex]12=3\cdot4=3\cdot2\cdot2[/latex].
Solution:
Step 1: Factor 12 as [latex]3\cdot4[/latex]. Now the factor tree looks like this below:
Step 2: Circle 3 since it is prime.
Step 3: Factor 4 as [latex]2\cdot2[/latex].
Step 4: Circle the 2s since they are prime.
Step 5: The prime factorization of 12 is the product of the circled leaves: [latex]2\cdot2\cdot3[/latex]. We write this as:
[latex]12=2\cdot2\cdot3[/latex].
Below is the other way we factored 12 shown by a factor tree. Notice that the two factor trees for 12 have the same root, 12, and the same prime leaves, 2, 2, 3, with different details.
|
Steps |
Factor Tree |
|---|---|
|
Step 1: Facrtor 12 as [latex]6 times 2[/latex]. |
|
|
Step 2: Circle 2 since it is prime. |
|
|
Step 3: Factor 6 as [latex]2 times 3[/latex] |
|
|
Step 4: Circle 3 and 2 since they are both prime. |
|
|
Step 5: The prime factorization of 12 is the product of the circled leaves [latex]3 \cdot 2 \cdot 2[/latex] |
[latex]12=2\cdot2\cdot3[/latex]. |
When we prime factor a number, it is important to determine if a factor is prime or not. If you aren’t sure whether a number is prime or composite and don’t know how to start factoring, use the divisibility tests to see if it is possible to divide by 2, 3, 5, 7, 11, etc. Make sure there are no factors before you circle it and decide it’s prime. Now for each of the numbers you’ve worked on in Exercise 1, show your work using a factor tree.
Use a factor tree to factor each of the following composite numbers into a product of primes. Write the prime factorization so the factors are written in ascending order (from smallest to largest). None of these numbers is prime. Show the individual steps. Show the factor tree under each problem.
| a. 45
Solution |
| b. 65
Solution |
| c. 200
Solution |
| d. 91
Solution |
| e. 76
Solution |
| f. 350
Solution |
| g. 189
Solution |
| h. 74
Solution |
| i. 512
Solution |
| j. 147
Solution
|
Prime Factor Test
The problem with trying to find the prime factorization is that sometimes it isn’t obvious if a number you are trying to factor is prime or not. For instance, it is not immediately obvious whether or not 517 is prime or composite. This is where divisibility tests come in handy. However, when the number is large, such as 517, the divisibility tests are not enough for us.
Actually, if you want to find the prime factorization of 517, you only need to check if 517 has any prime numbers as factors. You’ll need to try one prime at a time. Before we can do that, we need a list of prime numbers. Example 3 helps us to “sieve out” all the primes less than 100 on a hundred board.
List all of the prime numbers less than 100 using the hundred chart. You only need to use the divisibility tests for 2, 3, 5 and 7 at the most to check if any odd number less than 100 is prime. In other words, any composite number less than 100 has 2, 3, 5 or 7 as a factor. We’ll discuss the reason of it afterward.
[Probably reorganize the hundred boards from the table format to images.]
Solution:
We list out prime numbers from the ones less than 16, which we have found earlier in this section:
[latex]2, 3, 5, 7, 11, 13[/latex]
Now on the hundred board, we highlight the six primes we have found and cross out those less than 16 are not prime. The hundred board looks like this:
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 18 | 19 | 20 | ||||
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
Now, among all the numbers that are greater than 16, cross all multiples of 2, which means they are composite, not prime. The hundred board will become this:
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 21 | 23 | 25 | 27 | 29 | |||||
| 31 | 33 | 35 | 37 | 39 | |||||
| 41 | 43 | 45 | 47 | 49 | |||||
| 51 | 53 | 55 | 57 | 59 | |||||
| 61 | 63 | 65 | 67 | 69 | |||||
| 71 | 73 | 75 | 77 | 79 | |||||
| 81 | 83 | 85 | 87 | 89 | |||||
| 91 | 93 | 95 | 97 | 99 |
Next step, among the numbers greater than 16, cross all multiples of 3 because they are composite. While we are crossing them one by one, we notice that some numbers have already been crossed out, such as 18, 24, 36, etc. After crossing out all multiples of 3, the hundred board becomes this:
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 25 | 29 | |||||||
| 31 | 35 | 37 | 3 |
||||||
| 41 | 43 | 47 | 49 | ||||||
| 53 | 55 | 59 | |||||||
| 61 | 65 | 67 | |||||||
| 71 | 73 | 77 | 79 | ||||||
| 83 | 85 | 89 | |||||||
| 91 | 95 | 97 |
When crossing out all multiples of 5, we notice that, again, many of them are also multiples of 2 and/or 3 (such as 20, 30, 40, 45, etc), and they have been crossed out already. Now we get:
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | 3 |
|||||||
| 41 | 43 | 47 | 49 | ||||||
| 53 | 59 | ||||||||
| 61 | 67 | ||||||||
| 71 | 73 | 77 | 79 | ||||||
| 83 | 89 | ||||||||
| 91 | 97 |
Now among all the numbers that are greater than 16, cross out all multiples of 7. One more time, many numbers have been crossed out as multiples of 2, or 3, or 5. It is important to notice that the first number that we cross in this round is 49, which is [latex]7\cdot7[/latex]. And next one to be cross out is [latex]77=7\cdot11[/latex], and then [latex]91=7\cdot13[/latex. Other than these three, all the other multiples of 7 have been crossed out in the round for 2, 3, or 5. Now we get
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | 3 |
|||||||
| 41 | 43 | 47 | |||||||
| 53 | 59 | ||||||||
| 61 | 67 | ||||||||
| 71 | 73 | 79 | |||||||
| 83 | 89 | ||||||||
| 97 |
Now we can claim that all numbers left on the board uncrossed are primes. We highlight all the uncrossed numbers to indicate that they are all the primes less than 100:
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 | ||||||||
| 31 | 37 | 3 |
|||||||
| 41 | 43 | 47 | |||||||
| 53 | 59 | ||||||||
| 61 | 67 | ||||||||
| 71 | 73 | 79 | |||||||
| 83 | 89 | ||||||||
| 97 |
List all the primes less than 100 from the least to the greatest:
[latex]2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97[/latex]
Why can we make a claim in Example 3 that after this round of crossing out, all number left would be prime? In other words, why does any composite number less than 100 have 2, 3, 5 or 7 as a factor? Let's reflect on what we did when crossing out the multiples of 7. We've noticed that the first number crossed out only because of 7 is [latex]7^{2}=7\cdot7[/latex]. This shows that all other multiples of 7, including 14, 21, 28, 35, 42, are multiples of primes less than 7 and were crossed out in the first several rounds. Similarly, for the next prime number after 7, which is 11, the first composite number that is not a multiple of 2, 3, 5, or7 would be [latex]11^{2}[/latex], or 121. In other words, all number less than 121 must be either prime or a multiple of 2, 3, 5, or 7. This realization makes it easier to determine if a large number is prime or composite, and therefore, makes finding the prime factorization of a number much easier. It is called the Prime Factor Test. This is the formal way of stating that theorem.
Key Takeaway - Prime Factor Test
Prime Factor Test: To test for prime factors of a number n, one need only search for prime factors p of n, where [latex]p^{2} \leq n[/latex] ( or [latex]p \leq \sqrt{n}[/latex])
According to the prime factor test, we can get the following statements:
i. Since [latex]3^{2} = 9[/latex], any composite number < 9 has 2 as a factor. In other words, if a number less than 9 does not have 2 as a factor, then it must be prime, such as 5 and 7.
ii. Since [latex]5^{2} = 25[/latex], any composite number < 25 has 2 or 3 as a factor. In other words, if neither 2 nor 3 is factor of a number between 9 and 25, then it must be prime. For instance: 11, 13, 17, 19, and 23.
iii. Since [latex]7^{2} = 49[/latex], any composite number < 49 has 2, 3 or 5 as a factor. In other words, any of the numbers between 25 and 49 is either a multiple of 2, or 3, or 5, or a prime.
iv. Since [latex]11^{2} = 121[/latex], any composite number < 121 has 2, 3, 5 or 7 as a factor. In other words, if a number is not a multiple of any of the four primes, itself must be prime. That's why we can highlight all the left over numbers on the hundred board in Example 3.
The four statements above can help us check if a number less than 100 is a prime or not, without memorizing the list of primes we have got in Example 3. Now we can use the prime factor test to determine if 517 is prime and if it is not prime, we can then find its prime factorization.
Example 4
Determine if 517 is prime. If not, find the prime factorization of it.
Solution:
Step 1: Decide which primes should we check.
We need to test the divisibility of 517 by all primes that are less than the square root of 517.
Using calculator, we can find [latex]\sqrt{517} \approx{22.7}[/latex], and all the primes less than it are:
2, 3, 5, 7, 11, 13, 17, and 19.
Step 2: Check the divisibility of this number by the primes using the divisibility tests.
By observing the last digit of 517, we know that 2 and 5 are not factor of 517.
The digital root of 517 = 13-> 4 is not divisible by 3, so 3 is not factor of 517 either.
For 7: Double the last digit, 7, we get 14. Then we subtract 14 from 51 and get 37, which is not divisible by 7, so 7 is not a factor of 517 either.
For 11: Add the digits in the place that are even powers of 10, 5+7=12. Then subtract the digit in the place that is odd power of 10, 1 from 12, we get 11, which is divisible by 11. That means, 517 is divisible by 11.
Step 3: Conclude if the number is prime or composite. If it is composite, prime factor it.
Therefore, 517 is composite.
To factor it, we start with the first factor we just found, 11. To find another factor, we divide 517 by 11 and get 47. So, [latex]517=11\cdot47[/latex].
Now we look at the other factor, 47. As a number less than [latex]49=7^2[/latex], we can have a quick check for the divisibility of it by 2, 3, and 5, to find out that it is prime.
As a conclusion, the prime factorization of 517 is:
[latex]517=11\cdot47[/latex]
Now follow the steps in Example 4 to complete Exercise 3.
Exercise 3
For each number, determine the highest prime that might need to be checked to find the prime factorization of the number. Then, find the prime factorization. If it is prime, simply write the number itself, since that is the prime factorization.
|
a. 149 Highest prime to check: Prime factorization for 149: |
|
b. 273 Highest prime to check: Prime factorization for 149: |
|
c. 381 Highest prime to check: Prime factorization for 149: |
|
d. 437 Highest prime to check: Prime factorization for 149: |
|
e. 509 Highest prime to check: Prime factorization for 149: |
|
f. 613 Highest prime to check: Prime factorization for 149: |
|
g. 787 Highest prime to check: Prime factorization for 149:
|
Now, let's look at a range of numbers and figure out how to determine which ones are prime. For instance, let's determine which numbers between 350 and 370 are prime. First of all, only odd numbers in this range are prime. So, begin by listing the odd numbers as possibilities: 351, 353, 355, 357, 359, 361, 363, 365, 367 and 369. Next, note 355 and 365 can't be prime since it is divisible by 5. Now, you might use the divisibility test for 3 to cross off 351, 357, 363 and 369 note you can cross of multiples of 3 by crossing off every third odd number if you start at a multiple of 3. Now, our list is down to these possibilities: 353, 359, 361, 367 and 369. The highest prime you'd have to check is the prime number that is less than the square root of 369, which is 19. So, simply check the rest of the primes (7, 11, 13, 17 and 19 at most) on each of these numbers to determine which, if any, are prime. 353 is prime; 359 is prime; 361 is 19, 367 is prime. Therefore, 353, 359 and 367 are the numbers between 350 and 370 that are prime. Furthermore, you should be able to write the prime factorization for all the numbers between 350 and 370 that are composite.
Find the prime factorization for all the numbers between 280 and 295. If a number is prime, simply write the number itself.
| a. 280
Solution |
i. 288
Solution |
| b. 281
Solution |
j. 289
Solution |
| c. 282
Solution |
k. 290
Solution |
| d. 283
Solution |
l. 291
Solution |
| e. 284
Solution |
m. 292
Solution |
| f. 285
Solution |
n. 293
Solution |
| g. 286
Solution |
o. 294
Solution |
| h. 287
Solution
|
p. 295
Solution
|
Further Exploration
Twin primes are two consecutive odd numbers that are prime. For instance, 5 and 7 are twin primes, 11 and 13 are twin primes, 17 and 19 are twin primes. There is no pattern to determine how often twin primes come up. One unsolved question in mathematics is if there are a finite number of or infinitely many sets of twin primes.
More to work on:
i. From your work in exercise 11, list any sets of twin primes: _____
ii. Is it possible to have three odd numbers in a row that are prime? Why or why not?
Greatest Common Factor (GCF)
One use of prime factoring a set of numbers is so you can find the greatest common factor (GCF) and least common multiple (LCM) of them. Many people have trouble distinguishing between the greatest common factor and the least common multiple (LCM) because they don't think about what the words actually mean. The greatest common factor of a number is obviously a factor, but the adjective common describes that you want a factor that is common to all the numbers, and the adjective greatest describes that you want the very largest of the common factors of the numbers.
We are going to explore ways of finding the greatest common factor of two numbers, a and b. The notation to express this is GCF(a, b). It doesn't matter which number you list first in the parentheses – it's not an ordered pair.
Definition - Greatest Common Factor
We are going to explore different ways of finding the greatest common factor of two numbers.
First, we are going to explore one way to find the greatest common factor of 42 and 72.The notation to express this is GCF(42, 70).
Remember: it doesn't matter which number you list first in the parentheses, it's not an ordered pair. GCF(42, 70) means the same thing as GCF(70, 42). Both of them mean the greatest common factor of 42 and 70 is the largest number that is a factor of both 42 and 70.
One way of doing this is to list every single factor of each number and then pick the biggest one that is a factor of each.
Find GCF (42, 70).
Solution:
Step 1: List all of the factors of [latex]42[/latex] in ascending order:
[latex]42: 1, 2, 3, 6, 7, 14, 21, 42[/latex]
Step 2: List all of the factors of [latex]70[/latex] in ascending order:
[latex]70: 1, 2, 5, 7, 10, 14, 35, 70[/latex]
Step 3: List all of the factors that are common to both [latex]42[/latex]and [latex]70[/latex]:
[latex]1, 2, 7, 14[/latex]
Step 4: Find the greatest common factor listed in Step 3 and make the conclusion:
[latex]GCF(42, 70)=14[/latex]
Listing all of the factors of a given number is sometimes a difficult task. For instance, it's easy to miss a factor. One remedy is to prime factor the number first. To list all of the factors of 42, one might first prime factor 42 like this: [latex]2 \cdot 3 \cdot 7[/latex]. For a number to be a factor of 42, it must be composed of the prime factors listed. Of course, 1 is always a factor. Next, you'd check 2, and then 3, which are both factors. 4 is not a factor because if it were, [latex]2 \cdot 2[/latex] would be in the prime factorization! It's clear to see 5 is not a factor. 6 is a factor, since [latex]2 \cdot 3[/latex] is in the prime factorization. Continuing on, 7 is a factor, but 8 is not because [latex]2 \cdot 2 \cdot 2[/latex] is not in the prime factorization of 42. Neither is [latex]9[/latex]([latex]3 \cdot 3[/latex]), [latex]10[/latex]([latex]2 \cdot 5[/latex]), [latex]11[/latex], [latex]12[/latex] ([latex]2 \cdot 2 \cdot 3[/latex]), or [latex]13[/latex]. But [latex]14[/latex] is a factor of [latex]42[/latex] since [latex]2 \cdot 7[/latex] is in the prime factorization.
You can use this strategy as you check every number up to [latex]42[/latex], but that is still a lot of numbers to check, which you don't have to do. Here's a way to shorten the process a little more. Starting with the smallest factor 1, immediately list the other factor you'd have to multiply by that factor to get 42. So, we start with 1, 42. We check the next number, 2, and note it is a factor. To get the other factor that pairs up with 2, either divide 2 into 42, or simply look at the prime factorization of 42, with the 2 missing. There is [latex]3 \cdot 7[/latex] left, which is the other factor. So the list is now 1, 42, 2, 21.
Continuing, we note 3 is a factor. To get the other factor, either divide 42 by 3, or do it the easy way, which is to see what factors are left in the prime factorization of 42 with the 3 missing. Since there is a 2 and a 7, then the number that pairs up with 3 is 14.The list is now 1, 42, 2, 21, 3, 14.
Next, we note 4 and 5 are not factors. 6 is a factor since 2 and 3 ([latex]2 \cdot 3[/latex]) is in the prime factorization. 7 is the number that pairs up with 6. So, the list is now: 1, 42, 2, 21, 3, 14, 6, 7. If you were to continue, the next number to check would be 7, and it leads you back to the factor 6, which means we can stop. All the factors that are larger than 7 will already be in the list because there would have been a smaller factor that it paired up with already. Now, put the list of factors of 42 in ascending order: 1, 2, 3, 6, 7, 14, 21, 42.
The same procedure can be used to list all the factors of 70. First, write the prime factorization of 70: [latex]2 \cdot 5 \cdot 7[/latex]. You would start off with 1 and 70: 1, 70. Next, it's clear 2 is a factor that pairs up with 35. The list is now: 1, 70, 2, 35. Next discard 3 and 4 as factors, and note 5 is a factor. The factors left are 2 and 7, which multiplied together is 14. So the list is 1, 70, 2, 35, 5, 14. Continuing on, note 6 is not a factor, and 7 is. 7 pairs up with 10. The list is now: 1, 70, 2, 35, 5, 14, 7, 10. Continuing on, note that 8 is not a factor. The next number to check would be 9. But [latex]9^{2}[/latex] > 70, so all the factors higher are already in the list. Writing the list in ascending order, we get: 1, 2, 5, 7, 10, 14, 35, 70.
Make a note that in both of these examples, 42 and 70 each had exactly 3 prime numbers in the prime factorization. Let's work on a number with more prime factors.
Example 6 List All Factors Using Prime Factorization
Find all factors of 220 in ascending order using the prime factorization [latex]220=2 \cdot 2 \cdot 5 \cdot 11[/latex].
Solution:
Step 1: The first pair of factors is always [latex]1[/latex] and the number itself.
[latex]1[/latex]and [latex]220[/latex].
Step 2: List other factors in pairs.
Start from combining one, two, or three prime factors to get a leading factor of each pair, then multiply the others to get another factor of this pair.
[latex]2[/latex] is a factor; its pair is [latex]2 \cdot 5 \cdot 11=110[/latex].
[latex]4=2 \cdot 2[/latex] is a factor; its pair is [latex]5\cdot11=55[/latex].
[latex]5[/latex] is a factor; its pair is [latex]2 \cdot 2 \cdot 11=44[/latex].
[latex]10=2 \cdot 5[/latex] is a factor; its pair is [latex]2 \cdot 11=22[/latex].
[latex]11[/latex]is a factor; its pair is [latex]2 \cdot 2 \cdot 5=20[/latex].
Step 3: Stop and list all factors.
Notice that the leading factors of the pairs are called out in ascending order, whereas their pairs are in descending order. Now if we move on to make up more factors, such as [latex]2\cdot11=22[/latex], or [latex]2\cdot2\cdot5=20[/latex], we would find them ready shown in the previous pairs. That's the moment that we should stop because we have already found all factors of[latex]220[/latex] as below:
[latex]1, 220; 2, 110; 4, 55; 5, 44; 10, 22; 11, 20.[/latex]
Then we write these in ascending order, we get all the factors of [latex]220[/latex] as below:
[latex]1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, 220.[/latex]
Now, do the next exercises. Use prime factorization to do parts a. and b.
Find the greatest common factor of 92 and 115.
| a. List all of the factors of 92 in ascending order.
|
| b. List all of the factors of 115 in ascending order.
|
| c. List all of the factors that are common to both 92 and 115.
|
| d. Find the greatest common factor of 92 and 115 to fill in the blank: [latex]GCF(92, 115) =\underline{\quad}[/latex]
|
We can go through the similar procedure to find the greatest common factor of three or more numbers. Below is an exercise of finding GCF of three given numbers.
Exercise 6
Find the greatest common factor of 48, 54 and 63.
| a. List all of the factors of 48 in ascending order.
|
| b. List all of the factors of 54 in ascending order.
|
| c. List all of the factors of 63 in ascending order.
|
| d. List all of the factors that are common to 48, 54 and also 63.
|
| e. Find the greatest common factor of 48, 54 and 63 and fill in the bland: [latex]GCF(48, 54, 63) =\underline{\quad}[/latex].
|
As you might have realized, listing factors can still be a very time-consuming way to find the greatest common factor, especially if the numbers are very large or have a lot of factors.
It's time to get out your colored prime number squares and white composite number squares again. We'll be using these to prime factor sets of numbers, which can then be used to find the greatest common factor of a set of numbers. This method is usually faster than the one we just used.
Example 7
The goal of this next example is to find the greatest common factor of 42 and 72 using prime factorization with the prime and composite number squares.
Step 1: Use the squares to prime factor 42 and 72.
[latex]42 = 2 \cdot 3 \cdot 7[/latex] and [latex]72 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3[/latex]
Step 2: Draw a line and put the prime factors of 42 above it. Next to that, draw a line and put the prime factors of 72 above it.
Step 3: Look at the prime factorization of the numbers. Move every factor they have in common under the line. They should have the same exact factors under the line, and they should have no common factors left above the line.
Step 4: The product of the factors under a line is the greatest common factor of the numbers. In this case, 2 [latex]\cdot[/latex] 3, or 6, is the greatest common factor of 42 and 72.
Step 5: Use the correct notation to write the answer: GCF(42, 70) = 6.
The similar process works for us to find GCF of three numbers as shown in Example 8.
Example 8
This next example used the same steps to find the greatest common factor of 16, 24 and 36.
Step 1: Use the squares to prime factor 16, 24 and 36.
[latex]16 = 2 \cdot 2 \cdot 2 \cdot 2, 24 = 2 \cdot 2 \cdot 2 \cdot 3[/latex] and [latex]36 = 2 \cdot 2 \cdot 3 \cdot 3[/latex]
Step 2: Draw a line for each number and put the prime factors of each number above it.
 |
 |
 |
Step 3: Look at the prime factorization of the numbers. Move every factor that all three numbers have in common. There should be no factors left above the line that all three numbers have in common.
 |
 |
 |
Step 4: The product of the factors under a line is the greatest common factor of the numbers. In this case, [latex]2 \cdot 2[/latex], or 4, is the greatest common factor of 16, 24 and 36.
Step 5: Use the correct notation to write the answer: GCF(16, 24, 36) = 4.
Exercise 7
Use the steps shown in the previous two examples to find the greatest common factor of each problem. Show a picture of how the problem looks at step 3 where the prime factorization of the greatest common factor is shown under the line of each number you first prime factored.
|
a. GCF(42, 70) Show work below: |
|
b. GCF(92, 115) Show work below: |
|
c. GCF(48, 54, 63) Show work below: |
|
d. GCF(306, 340) Show work below: |
|
e. GCF(125, 275, 400) Show work below: |
|
f. GCF(126, 168, 210) Show work below: |
Example 9
[latex]X[/latex], [latex]Y[/latex] and [latex]Z[/latex] are three large numbers that have been prime factored:
[latex]X = 2^{5} \cdot 3^{4} \cdot 7^{2} \cdot 11^{8} \cdot 13^{3}[/latex]
[latex]Y = 2^{4} \cdot 3^{5} \cdot 5^{3} \cdot 7^{7} \cdot 13^{2}[/latex]
[latex]Z = 2^{6} \cdot 3 \cdot 5^{5} \cdot 11^{3} \cdot 13^{4}[/latex]
Find the prime factorization (exponential notation is okay) of the greatest common factor of [latex]X[/latex], [latex]Y[/latex] and [latex]Z[/latex].
Solution:
Step 1: List the common prime factors (without exponents) of [latex]X[/latex], [latex]Y[/latex] and [latex]Z[/latex].
The common prime factors that are in all three prime factorizations are [latex]2[/latex], [latex]3[/latex], and [latex]13[/latex].
Step 2: Determine how many of each prime factor is common to [latex]X[/latex], [latex]Y[/latex] and [latex]Z[/latex].
Since[latex]X[/latex]has[latex]5[/latex] factors of [latex]2[/latex], [latex]Y[/latex] has [latex]4[/latex] factors of [latex]2[/latex], and [latex]Z[/latex] has [latex]6[/latex] factors of [latex]2[/latex], they only have [latex]4[/latex] factors of [latex]2[/latex] in common. Similarly, they only have one factor of [latex]3[/latex] in common, and [latex]2[/latex] factors of [latex]13[/latex] in common.
Step 3: Make a conclusion by writing these exponents on the common prime factors to get the [latex]GCF[/latex] of the three numbers.
[latex]GCF(X, Y, Z) = 2^{4} \cdot 3 \cdot 13^{2}[/latex]
Did you notice that if you list the factors they have in common without exponents, you put on the smallest exponent they have in common for each prime?
Write the prime factorization of the greatest common factor of the set of numbers. For those that are factored with letters, assume each letter represents a different prime number.
a. If [latex]X = 2^{4} \cdot 3^{2} \cdot 7^{6} \cdot 11^{3} \cdot 13^{2}[/latex] and [latex]Y = 2^{5} \cdot 3^{6} \cdot 5^{4} \cdot 7^{6} \cdot 13^{3}[/latex],
[latex]GCF(X, Y) = \underline{\qquad\qquad\qquad\qquad}[/latex]
b. If [latex]X = 3^{4} \cdot 5^{2} \cdot 7^{6}[/latex] and [latex]Y = 2^{5} \cdot 3^{6} \cdot 5^{6} \cdot 7^{3}[/latex] and [latex]Z = 2^{4} \cdot 3^{5} \cdot 5^{4}[/latex],
[latex]GCF(X, Y, Z) =\underline{\qquad\qquad\qquad\qquad}[/latex]
c. If [latex]X = a^{4} \cdot b^{2} \cdot c^{6} \cdot d^{3} \cdot e^{2}[/latex] and [latex]Y = a^{5} \cdot c^{3} \cdot d^{4} \cdot e^{6} \cdot f^{3}[/latex],
[latex]GCF(X, Y) = \underline{\qquad\qquad\qquad\qquad}[/latex]
d. If [latex]X = a^{4} \cdot b \cdot c^{4} \cdot d^{3}[/latex] and [latex]Y = a^{5} \cdot b^{3} \cdot d^{4} \cdot e^{6}[/latex] and [latex]Z = a^{2} \cdot c^{3} \cdot d^{7} \cdot f^{3}[/latex],
[latex]GCF(X, Y, Z) =\underline{\qquad\qquad\qquad\qquad}[/latex]
If two numbers have no factors in common, they are called relatively prime. In other words, if [latex]GCF(a, b) = 1[/latex], then [latex]a[/latex] and [latex]b[/latex] are relatively prime. The numbers, [latex]a[/latex] and [latex]b[/latex], might both be prime, both be composite, or one might be prime and the other composite. Two unequal primes are always relatively prime. For example, considering two primes 3 and 5, we have [latex]GCF(3, 5)=1[/latex], so they are relatively prime. Generally speaking, if [latex]x[/latex] and [latex]y[/latex] are different prime numbers, then [latex]GCF(x, y) =1[/latex], which means they are relatively prime. In general, one prime number and one composite number or two composite number might be relatively prime as well. For instance, although 14 and 15 are both composite numbers, we have GCF(14, 15) =1 because [latex]14=2\cdot7[/latex] and [latex]15=3\cdot5[/latex]. Therefore, 14 and 15 are relatively prime.
Exercise 9
a. Give an example of two composite numbers that are relatively prime:
b. Write a prime number and composite number that are relatively prime:
Further Exploration:
1. Assume GCF(28, x) = 1. List all prime numbers that must not be factors of x. Then give three examples (numbers) of what x could equal.
2. If m is a whole number, find the following:
a. [latex]GCF(2m, 3m) =\underline{\qquad\qquad}[/latex]
b. [latex]GCF (4m, 10m) =\underline{\qquad\qquad}[/latex]
c. [latex]GCF(m, m) =\underline{\qquad\qquad}[/latex]
d. [latex]GCF( m, 1) =\underline{\qquad\qquad}[/latex]
e. [latex]GCF(m, 0) =\underline{\qquad\qquad}[/latex]
The Old Chinese Method and The Euclidean Algorithm
Trying to find the greatest common factor of two large numbers by prime factorization is sometimes quite time-consuming. There are two other algorithms you can use that we'll use. One is called The Old Chinese Method, and the other is The Euclidean Algorithm. Both of these methods use a fact we can prove using what we know about divisibility, which says that the greatest common factor of two numbers is equal to the greatest common factor of the smaller number, and the difference of the original two numbers; i.e., if [latex]x\geq y[/latex], then [latex]GCF(x, y) = GCF(y, x – y)[/latex].
Prove the following statement: Let [latex]a\geq b[/latex]. If [latex]c|a[/latex] and [latex]c|b[/latex], then [latex]c|(a – b)[/latex].
Proof: If [latex]c|a[/latex], then [latex]cn=a[/latex] for some whole number, [latex]n[/latex]. If [latex]c|b[/latex], then [latex]cm=b[/latex] for some whole number, [latex]m[/latex]. Using these substitutions for [latex]a[/latex] and [latex]b[/latex], we get that [latex]a-b=cn-cm=c(n-m)[/latex], which shows [latex]c[/latex] is indeed a factor of [latex]a-b[/latex]. Therefore, [latex]c|(a – b)[/latex].
This theorem can be used to show that if [latex]a\geq b[/latex], then GCF(a, b) = GCF(b, a – b). The above theorem states that if c is a factor of two numbers, then it is also a factor of their difference. Hence, if c is a common factor of a and b, where [latex]a\geq[/latex] b, then c is also a common factor of b and a – b. Since every common factor of a and b is also a common factor of ba and a – b, the pairs (a, b) and (b, a – b) have the same common factors. So, GCF(a, b) and GCF(b, a – b) must also be the same number.
The Old Chinese Method employs the fact that GCF(a, b) = GCF(b, a – b).
Note three more properties:
GCF(x, x) = x: GCF(x, x) states that the greatest common factor of the same two numbers is itself. That should be clear since x is the greatest factor of each number, so each has x as the greatest common factor.
GCF(x, 0) = x: GCF(x, 0) = x, is true since every number is a factor of zero. So, since x is the greatest factor of x, then x is the greatest common factor of x and 0.
GCF(x, 1) = 1: GCF(x, 1) = 1 is true since 1 is a factor of every number, including x, and 1 is the only factor of 1. Therefore, 1 must be the greatest common factor of 1 and x.
Old Chinese Method of finding the greatest common factor of two numbers:
Write the GCF of the two numbers in parentheses (remember the order of the numbers is irrelevant). Let that equal the GCF of the smaller of the two numbers, and the difference of the original two numbers. If the numbers in the parentheses are the same, that number is the GCF; if one the new numbers is 1, 1 is the GCF. Otherwise, repeat the process until the two numbers are the same, or 1 is one of the numbers. An example is shown below. On the right is an explanation of how we obtain the two new numbers in parentheses. The new numbers are underlined in the explanation.
Find [latex]GCF(546, 390)[/latex] using the Old Chinese Method.
Solution:
|
[latex]GCF(546, 390)[/latex] |
[latex]= GCF(390, 156)[/latex] |
([latex]\underline{390}[/latex]is smaller than [latex]546[/latex], [latex]\underline{156} = 546 – 390[/latex]) |
| [latex]= GCF(156, 234)[/latex] | ([latex]\underline{156}[/latex] is smaller than [latex]390[/latex], [latex]\underline{234} = 390 – 156[/latex]) | |
| [latex]= GCF(156, 78)[/latex] | ([latex]\underline{156}[/latex] is smaller than [latex]234[/latex], [latex]\underline{78} = 234 – 156[/latex]) | |
| [latex]= GCF(78, 78)[/latex] | ([latex]\underline{78}[/latex] is smaller than [latex]156[/latex], [latex]\underline{78} = 156 – 78[/latex]) | |
| [latex]= 78[/latex]
|
[latex]78[/latex] is the [latex]GCF(78, 78)[/latex]. The answer is a number!
|
Therefore, [latex]GCF(546, 390) = 78.[/latex]
Check:
First, make sure 78 is a factor of 546 and 390: [latex]546 = 78\cdot 7[/latex] and [latex]390 = 78 \cdot 5[/latex]. Second, check to make sure the other factors of each (7 and 5) are relatively prime. If so, then 78 is not only a factor of 546 and 390, but is in fact the greatest common factor of each since they have no other common factors (because 7 and 5 have no common factors).
Another example is shown below. On the right is an explanation of how we obtain the two new numbers (underlined) in parentheses. You do not need to write that out.
Find [latex]GCF(1200, 504)[/latex] using the Old Chinese Method.
Solution:
|
[latex]GCF(1200, 504)[/latex] |
[latex]= GCF(504, 696)[/latex] |
([latex]\underline{504}[/latex]is smaller than [latex]1200[/latex], [latex]\underline{696} = 1200 – 504[/latex]) |
| [latex]= GCF(504, 192)[/latex] | ([latex]\underline{504}[/latex] is smaller than [latex]696[/latex], [latex]\underline{192} = 696 – 504[/latex]) | |
| [latex]= GCF(192, 312)[/latex] | ([latex]\underline{192}[/latex] is smaller than [latex]504[/latex], [latex]\underline{312} = 504 – 192[/latex]) | |
| [latex]= GCF(192, 120)[/latex] | ([latex]\underline{192}[/latex] is smaller than [latex]312[/latex], [latex]\underline{120} = 312 – 192[/latex]) | |
| [latex]= GCF(120, 72)[/latex] | ([latex]\underline{120}[/latex] is smaller than [latex]192[/latex], [latex]\underline{72} = 192 – 120[/latex]) | |
| [latex]= GCF(72, 48)[/latex] | ([latex]\underline{72}[/latex] is smaller than [latex]120[/latex], [latex]\underline{48} = 120 – 72[/latex]) | |
| [latex]= GCF(48, 24)[/latex] | ([latex]\underline{48}[/latex] is smaller than [latex]72[/latex], [latex]\underline{24} = 72 – 48[/latex]) | |
| [latex]= GCF(24, 24)[/latex] | ([latex]\underline{24}[/latex] is smaller than [latex]48[/latex], [latex]\underline{24} = 72-48[/latex]) | |
| [latex]= 24[/latex]
|
[latex]24[/latex] is the [latex]GCF(24, 24)[/latex]. The answer is a number!
|
Therefore, GCF(1200, 504) = 24.
Check: First, make sure 24 is a factor of 1200 and 504: 1200 = [latex]24 \cdot 50[/latex] and [latex]502 = 24 \cdot 21[/latex]. Second, check to make sure the other factors of each (25 and 21) are relatively prime. If so, then 24 is not only a factor of 1200 and 504, but is in fact the greatest common factor of each since they have no other common factors (because 25 and 21 have no common factors.)
Here is one more example without the explanation on its right side. This is how we write out the solution when we use the Old Chinese Method to find the greatest common factor of two numbers.
Find [latex]GCF(667, 437)[/latex] using the Old Chinese Method.
Solution:
| [latex]GCF(667, 437)[/latex] | [latex]= GCF(437, 230)[/latex] | |
| [latex]= GCF(230, 207)[/latex] | ||
| [latex]= GCF(207, 23)[/latex] | ||
| [latex]= GCF(23, 184)[/latex] | ||
| [latex]= GCF(23, 161)[/latex] | ||
| [latex]= GCF(23, 138)[/latex] | ||
| [latex]= GCF(23, 115)[/latex] | ||
| [latex]= GCF(23, 92)[/latex] | ||
| [latex]= GCF(23, 69)[/latex] | ||
| [latex]= GCF(23, 46)[/latex] | ||
| [latex]= GCF(23, 23)[/latex] | ||
| [latex]= 23[/latex] | Remember: The answer is a number! |
Therefore, GCF(667, 437) = 23.
Check: First, make sure 23 is a factor of 667 and 437: [latex]667 = 23 \cdot 29[/latex] and [latex]437 = 23 \cdot 19[/latex]. Second, check to make sure the other factors of each (29 and 19) are relatively prime. If so, then 23 is not only a factor of 667 and 437, but is in fact the greatest common factor of each since they have no other common factors (because 29 and 19 have no common factors.)
A comment: You could have obtained the greatest common factor of the previous three examples by prime factoring. Often, this is a lengthy process for large numbers that look like they might be prime, as in the last example. Therefore, the Old Chinese provides an alternative way to obtain the greatest common factor. After doing a few exercise using this method, we'll explore another alternate method, called the Euclidean Algorithm, which is related to, but usually takes less steps than, the Old Chinese Method.
Exercise 10
Use the Old Chinese Method to compute the greatest common factor of the numbers given. Use correct notation, and show each step. State the answer. Then, show how you check your answer. Use the previous example as a model to do these problems.
a.
| [latex]GCF(143, 91)[/latex] | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
b.
| [latex]GCF(468, 378)[/latex] | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
c.
| GCF(504, 180) | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
Using the Chinese Method could be quite tedious. Take a further look at the solution in the Example 11:
|
[latex]GCF(1200, 504)[/latex] |
[latex]= GCF(504, 696)[/latex] |
([latex]\underline{504}[/latex]is smaller than [latex]1200[/latex], [latex]\underline{696} = 1200 – 504[/latex]) |
| [latex]= GCF(504, 192)[/latex] | ([latex]\underline{504}[/latex] is smaller than [latex]696[/latex], [latex]\underline{192} = 696 – 504[/latex]) | |
| [latex]= GCF(192, 312)[/latex] | ([latex]\underline{192}[/latex] is smaller than [latex]504[/latex], [latex]\underline{312} = 504 – 192[/latex]) | |
| [latex]= GCF(192, 120)[/latex] | ([latex]\underline{192}[/latex] is smaller than [latex]312[/latex], [latex]\underline{120} = 312 – 192[/latex]) | |
| [latex]= GCF(120, 72)[/latex] | ([latex]\underline{120}[/latex] is smaller than [latex]192[/latex], [latex]\underline{72} = 192 – 120[/latex]) | |
| [latex]= GCF(72, 48)[/latex] | ([latex]\underline{72}[/latex] is smaller than [latex]120[/latex], [latex]\underline{48} = 120 – 72[/latex]) | |
| [latex]= GCF(48, 24)[/latex] | ([latex]\underline{48}[/latex] is smaller than [latex]72[/latex], [latex]\underline{24} = 72 – 48[/latex]) | |
| [latex]= GCF(24, 24)[/latex] | ([latex]\underline{24}[/latex] is smaller than [latex]48[/latex], [latex]\underline{24} = 72-48[/latex]) | |
| [latex]= 24[/latex]
|
[latex]24[/latex] is the [latex]GCF(24, 24)[/latex]. The answer is a number!
|
In the beginning of this example, GCF(1200, 504), we had to subtract 504 twice until we got GCF(504, 192). Then, notice once we wrote GCF(504, 192), we had to subtract 192 twice until we got GCF(192, 120). Basically, we do repeated subtraction until we get a number smaller than the one we are subtracting. Repeated subtraction is actually division. Note that [latex]1200 \div 504 = 2[/latex] remainder 192. On the second step, we see GCF(504, 192), which has the smaller of the numbers in the original parentheses (504), and the remainder after dividing the larger number (1200) by the smaller number (504). Note that [latex]504 \div 192 = 2[/latex] remainder 120. Look at the fourth step: we see GCF(192, 120), which has the smaller of the numbers in GCF(504, 192), and the remainder after dividing the larger number (504) by the smaller number (192). The Euclidean Algorithm uses division instead of repeated subtraction to shorten the steps.
How to use the Euclidean Algorithm to find the greatest common factor of two numbers:
Write the GCF of the two numbers in parentheses (remember the order of the numbers is irrelevant). The smaller of the two numbers will be one of the numbers in the next parentheses. To get the other number, divide the larger number by the smaller number, and put the remainder in parentheses. If the the smaller number is a factor of the larger number, that means it will divide evenly, so there will be no remainder. That means the remainder is 0. Remember to put the remainder in the parentheses, not the quotient! If one of the new numbers in the parentheses is zero, the other number is the GCF; if one the new numbers is 1, 1 is the GCF. Otherwise, repeat the process until one of the two numbers is 0 or 1. An example is shown below. This is the first example we did using the Old Chinese Method. You might want to look back and compare. On the right is an explanation of how I obtained the two new numbers in parentheses.
Use the Euclidean Algorithm to find [latex]GCF(546, 390)[/latex].
| GCF(546, 390) | = GCF(390, 156) | (390 is smaller than 546, [latex]546 \div 390[/latex] = 1 r 156) |
| = GCF(156, 78) | (156 is smaller than 390, [latex]390 \div 156[/latex] = 2 r 78) | |
| = GCF(78, 0) | (78 is smaller than 156, [latex]156 \div 78[/latex] = 2 r 0) | |
| = 78 | Put the remainder (0), NOT 2, in the parentheses! | |
| 78 is the GCF(78, 78); The answer is a number! |
Therefore, GCF(546, 390) = 78
Check: First, make sure 78 is a factor of 546 and 390: [latex]546 = 78 = \cdot 7[/latex] and [latex]390 = 78 \cdot 5[/latex]. Second, check to make sure the other factors of each (7 and 5) are relatively prime. If so, then 78 is not only a factor of 546 and 390, but is in fact the greatest common factor of each since they have no other common factors (because 7 and 5 have no common factors).
Below is another example – we did this earlier using the Old Chinese Method. On the right is an explanation of how I obtained the two new numbers in parentheses. You do not need to write that out.
Use the Euclidean Algorithm to find [latex]GCF(667, 437)[/latex].
| GCF(667, 437) | = GCF(437, 230) | (437 is smaller than 667, [latex]667 \div 437 = 1[/latex] r 230) |
| = GCF(230, 207) | (230 is smaller than 437, [latex]437 \div 230 = 1[/latex] r 207) | |
| = GCF(207, 23) | (207 is smaller than 230, [latex]230 \div 207[/latex] = 1 r 23) | |
| = GCF(23, 0) | (23 is smaller than 207, [latex]207 \div 23[/latex] = 9 r 0) | |
| = 23 | Put the remainder (0), NOT 9, in the parentheses! | |
| Remember: The answer is a number! |
Therefore, GCF(667, 437) = 23
Check: First, make sure 23 is a factor of 667 and 437: 667 = [latex]23 \cdot 29[/latex] and [latex]437 = 23 \cdot 19[/latex]. Second, check to make sure the other factors of each (29 and 19) are relatively prime. If so, then 23 is not only a factor of 667 and 437, but is in fact the greatest common factor of each since they have no other common factors (because 29 and 19 have no common factors.)
CAUTION: THE MOST COMMON MISTAKE PEOPLE MAKE WHEN USING THE EUCLIDEAN ALGORITHM IS ON THE LAST STEP, WHEN THE SMALLER NUMBER DIVIDES EVENLY INTO THE LARGER NUMBER, WHICH MEANS THE REMAINDER IS ZERO. IT DOESN'T MATTER WHAT THE QUOTIENT IS – IT'S THE REMAINDER THAT MATTERS – 0 GOES IN THE PARENTHESES!!! Also, zero is not a factor of any number except zero, so the GCF can't be zero. On the other hand, every number is a factor of zero. So, when zero is one of the numbers in parentheses, the other number is the GCF. REMEMBER TO ALWAYS CHECK YOUR Answer!!!
Use the Euclidean Algorithm to compute the greatest common factor of the numbers given. Use correct notation, and show each step. State the answer. Then, show how you check your answer. Use the previous example as a model to do these problems. These are the same exercises you did using the Old Chinese Method in exercise 27. You might want to compare the two methods when you are done. Of course, the answer should be the same.
a.
| [latex]GCF(143, 91)[/latex] | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
b.
| [latex]GCF(468, 378)[/latex] | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
c.
| GCF(504, 180) | [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | Show the check here: |
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]= GCF (\underline{\qquad},\underline{\qquad} )[/latex] | ||
| [latex]=\underline{\qquad}[/latex] |
Now we have learned three ways to find the greatest common factor of two numbers: (i) by prime factoring, (ii) the Old Chinese Method, or (iii) the Euclidean Algorithm.
Exercise 12
For each pair of numbers, find the greatest common factor i) by prime factorization, ii) by the Old Chinese Method, and c) by the Euclidean Algorithm. After you write the answer, iii) show how to check the answer.
a. Find [latex]GCF(418, 88)[/latex].
Solution
b. Find [latex]GCF(527, 465)[/latex].
Solution
c. Find [latex]GCF(353, 213)[/latex].
Solution