Greatest Common Factor – Explanation & 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 second factor 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.
The 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 set’s numbers 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 each factor’s factors 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.
Using repeated division, also known as recursive division, to find the greatest common factor is similar to prime factorization, but it takes unnecessary steps. It works by dividing every term in a set by a common factor (not necessarily the greatest) until the numbers 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 reason why repeated division can be more efficient than prime factorization.
If two numbers are coprime, then their greatest common factor is 1.
The greatest common factor of a set of numbers can 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 number’s last two digits 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.