JUMP TO TOPIC
Greatest Common Factor – Explanation And Practical Examples
Knowing the greatest common factor of two numbers can help when simplifying fractions or factoring mathematical expressions. The greatest common factor is also used in one method for finding the least common multiple.
What’s the Greatest Common Factor
The greatest common factor of a set of non-zero numbers is the largest positive whole number that evenly divides each number in the set. The greatest common factor is abbreviated as GCF. It is also sometimes referred to as the greatest common divisor.
Recall that one number is a factor of a second number if you can divide the second by the first without a remainder. That is, the quotient of the two numbers is an integer.
How to Find the Greatest Common Factor
There are several different ways to find the Greatest Common Factor of a set of numbers: listing positive factors, using prime factorization, and repeated division.
In general, listing positive factors works best when dealing with two low-value numbers without many factors.
Using prime factorization can work well when dealing with sets that have more than two numbers.
Repeated division is often the fastest method for finding the greatest common factor of a set with two higher-valued numbers.
Listing Positive Factors
To find the greatest common factor with this method, list out all of the positive factors for the numbers in the set in order from least to greatest. Then, note the largest factor that the numbers in the set have in common. This is the greatest common factor.
For example, to find the greatest common factor of 10 and 15, list out the factors of each, and note the largest one that the two have in common, as shown. In this case, 5 is the greatest common factor.
This method can quickly become tedious for numbers that have many factors. It is also easy to overlook a factor when listing them out, making this method prone to errors. For these reasons, listing positive factors works best for “familiar” numbers, such as those that students generally memorize in their times tables.
Using Prime Factorization
To use prime factorization to find the greatest common factor, first the prime factorization of every number in the set. Then, multiply together any primes that appear in all of the factored forms. This product is the greatest common factor of the set.
Recall that you can find the prime factorization of any number by using a factor tree. This is the factor tree for 196.
The prime factorization is the product of all of the primes in the factor tree. For 196, the prime factorization is 2x2x7x7.
To use prime factorization to find the greatest common factor of 144 and 96, first, make a factor tree for both numbers, as shown.
The prime factorization of 144 then is 2x2x2x2x3x3, and the prime factorization of 96 is 2x2x2x2x2x3.
The common primes are 2x2x2x2x3.
Multiplying those together yields 48, the greatest common factor.
Repeated Division
Using repeated division, also known as recursive division, to find the greatest common factor is similar to using prime factorization, but it takes out unnecessary steps.
It works by dividing every term in a set by a common factor (not necessarily the greatest), until the numbers that remain have no common factors except 1. Such numbers are called coprime. The greatest common factor will be the product of all the common factors used in the repeated division.
For this reason, it is important to keep a tally of the factors used. The easiest way to do that is to set up a table like the one used below to find the greatest common factor of 1200 and 1960.
In this example, first divide 1200 and 1960 by 10 to get 120 and 196 respectively. Record these numbers in the table.
Divide 120 and 196 by 2 to get 60 and 98 respectively. Record these numbers in the table as well.
Then, divide 60 and 98 each by 2 to get 30 and 49 respectively. This should also be recorded in the table.
Since 49 is only divisible by 1, 7, and 49, and 30 is not divisible by 7 or 49, 30 and 49 are coprime. Stop dividing at this point.
Then, multiply the numbers in the left-hand column together to find the GCF. In this case, 10x2x2=40, so 40 is the greatest common factor of 1200 and 1960.
Note that the factors used to divide the set of numbers do not have to be prime, and this is one of the reasons repeated division can be more efficient than prime factorization.
Tips
If two numbers are coprime, then their greatest common factor is 1.
It is possible for the greatest common factor of a set of numbers to be one of the numbers in the set. For example, the greatest common factor of 10 and 20 is 10.
There are some tricks for quickly determining whether a number is divisible by 2, 3, 4, 5, 6, 9, and 10 that can help with any of the three methods for finding the greatest common factor.
- 2: All even numbers are divisible by 2
- 3: A number is divisible by 3 if the sum of its digits is a multiple of 3. For example, 178923 is divisible by 3 because 1+7+8+9+2+3=30, and 30 is divisible by 3.
- 4: A number is divisible by 4 if the last two digits of the number are divisible by 4. For example, 1234564 is divisible by 4 because 64 is divisible by 4.
- 5: A number is divisible by 5 if it ends in a 5 or a 0.
- 6: A number is divisible by 6 if it is divisible by 2 and 3.
- 9: A number is divisible by 9 if the sum of its digits adds to a multiple of 9. For example, 18297 is divisible by 9 because 1+8+2+9+7=27, and 27 is divisible by 9.
- 10: A number is divisible by 10 if it ends in 0.
Practice
Listing the Factors
Questions
- Find the greatest common factor of 18 and 27.
- Find the greatest common factor of 25, 75, and 125.
- Find the greatest common factor of 19 and 32.
Solutions
The positive factors of 18 are 1, 2, 3, 6, 9, and 18.
- The positive factors of 27 are 1, 3, 9, and 27.
The greatest number that appears in both lists is 9, so that is the greatest common factor. - The positive factors of 25 are 1, 5, and 25.
The positive factors of 75 are 1, 3, 5, 25, and 75.
The positive factors of 125 are 1, 5, 25, and 125.
The greatest number that appears in all three lists is 25, so that is the greatest common factor. - The positive factors of 19 are 1 and 19.
The positive factors of 32 are 1, 2, 4, 8, 16, and 32.
The greatest and only number that appears in both lists is 1, so that is the greatest common factor. Therefore, 19 and 32 are coprime.
Using Prime Factorization
Questions
- Find the greatest common factor of 1272 and 294.
- Find the greatest common factor of 900, 360, and 729.
- Find the greatest common factor of 72, 144, 258, and 824.
Solutions
- The prime factorization of 1272 is 2x2x2x3x53.
The prime factorization of 294 is 2x3x7x7.
Both 1272 and 294 contain one 2 and one 3, so the greatest common factor is 2×3=6. - The prime factorization of 900 is 2x2x3x3x5x5.
The prime factorization of 360 is 2x2x2x3x3x5.
The prime factorization of 729 is 3x3x3x3x3x3.
All three factorized forms include two 3s, so the greatest common factor is 3×3=9. - The prime factorization of 72 is 2x2x2x3x3.
The prime factorization of 144 is 2x2x2x2x3x3.
The prime factorization of 258 is 2x3x43.
The prime factorization of 824 is 2x2x2x103.
In this case, the only number that appears in all four factorized forms is 2, so that is the greatest common factor.
Using Repeated Division
Questions
- Use repeated division to find the greatest common factor of 896 and 976.
- Use repeated division to find the greatest common factor of 7740 and 7380.
- Use repeated division to find the greatest common factor of 180, 144, and 108.
Solutions
- Divide 896 and 976 by 2 to get 448 and 488 respectively.
Divide 448 and 488 by 2 to get 224 and 244 respectively.
Divide 224 and 244 by 2 to get 112 and 122 respectively.
Divide 112 and 122 by 2 to get 56 and 61 respectively.
Since 61 is prime, 56 and 61 are coprime.
Therefore, the greatest common factor is 2x2x2x2=16. - Divide 7740 and 7380 by 10 to get 774 and 738 respectively.
Divide 774 and 738 by 2 to get 387 and 369 respectively.
Divide 387 and 369 by 9 to get 43 and 41 respectively.
Since 43 and 41 are both prime, the greatest common factor is 10x2x9=180. - Divide 180, 144, and 108 by 12 to get 15, 12, and 9 respectively.
Divide 15, 12, and 9 by 3 to get 5, 4, and 3 respectively.
5, 4, and 3 have no common factors, so the greatest common factor of 180, 144, and 108 is 12×3=36.