Greatest Common Factor
Pronunciation: /greɪt.est ˈkɒm.ən ˈfæk.tər/ Explain
A greatest common factor is the largest number or
expression
that is a factor of two or more numbers or expressions. A greatest
common factor can also be called a
greatest common divisor.
In British English, the greatest common factor is called the
highest common factor
and the greatest common divisor is called the
highest common divisor. The
abbreviations for these terms are:
Term | Abbreviation |
greatest common factor | gcf |
greatest common divisor | gcd |
highest common factor | hcf |
highest common divisor | hcd |
Table 1: Abbreviations |
The greatest common factor of 8 and 12 is 4.
The greatest common factor of (x+3)(x-2) and
(2x-6)(x-2) is (x-2).
How to Find a Greatest Common Factor Using
Prime Factorization
There are two steps to finding a greatest common factor of numbers or expressions:
- Find all
prime factors
of each of the numbers or expressions.
- Identify every prime factor that is common to all of the numbers or expressions.
Example: Find the greatest common factor of 60 and 70.
- The prime factorization of 60 is 2·2·3·5.
The prime factorization of 70 is 2·5·7.
- The common factors are 2 and 5. The greatest
common factor is 2·5 = 10.
Understanding Check
For each step, find the answer, then click on
Click for answer.
- What is the greatest common factor of 12 and 6?
- What are the prime factors of 12?
Click for answer
The prime factors of 12 are 2, 2 and 3. This can also be written 2^{2}·3 = 12.
- What are the prime factors of 6?
Click for answer
The prime factors of 6 are 2 and 3. This can also be written 2·3 = 6.
- What prime factors are
common
to 6 and 12?
Click for answer
The common prime factors of 6 and 12 are 2 and 3.
- Multiply the prime factors together to get the greatest common factor.
Click for answer
2·3 = 6. The greatest common factor of 6 and 12 is 6.
- What is the greatest common factor of 12 and 6?
- What are the prime factors of 12?
Click for answer
The prime factors of 12 are 2, 2 and 3. This can also be written 2^{2}·3 = 12.
- What are the prime factors of 6?
Click for answer
The prime factors of 6 are 2 and 3. This can also be written 2·3 = 6.
- What prime factors are
common
to 6 and 12?
Click for answer
The common prime factors of 6 and 12 are 2 and 3.
- Multiply the prime factors together to get the greatest common factor.
Click for answer
2·3 = 6. The greatest common factor of 6 and 12 is 6.
- What is the greatest common factor of 9 and 12?
- What are the prime factors of 9?
Click for answer
The prime factors of 9 are 3 and 3. This can also be written 3^{2} = 9.
- What are the prime factors of 12?
Click for answer
The prime factors of 12 are 2, 2 and 3. This can also be written 2^{2}·3 = 12.
- What prime factors are
common
to 9 and 12?
Click for answer
The common prime factor of 9 and 12 is 3.
- Since there is only one common prime factor, the greatest common factor is the prime factor.
Click for answer
The greatest common factor of 9 and 12 is 3.
Euclidean Algorithm
The Euclidean algorithm is a quick method of
finding the greatest common factor of two numbers. It is based on the fact
that the greatest common factor of two numbers is the same as the greatest
common factor of either number and their difference. For example, use 51 and 85.
gcf(51,85) = 17. Now subtract 51 from 85. 85 - 51 = 34.
gcf(85,34) = 17 and gcf(51,34) = 17.
The Euclidean algorithm uses this fact to find the greatest common factor. To find
the greatest common factor using the Euclidean algorithm:
Iteration | First Number | Second Number | Difference | Discussion |
1 | 124 | 217 | 217 - 124 = 93 | Since 193 and 124 are the smaller of the three numbers, use them for the next step. |
2 | 124 | 93 | 124 - 93 = 31 | Since 93 and 31 are the smaller of the three numbers, use them for the next step. |
3 | 93 | 31 | 93 - 31 = 62 | Since 62 and 31 are the smaller of the three numbers, use them for the next step. |
4 | 62 | 31 | 62 - 31 = 31 | Since 31 and 31 are the smaller of the three numbers, use them for the next step. |
5 | 31 | 31 | 31 - 31 = 0 | Since the difference is zero, the greatest common factor of 217 and 124 is 31. |
Table 2 |
References
- McAdams, David E.. All Math Words Dictionary, greatest common factor. 2nd Classroom edition 20150108-4799968. pg 87. Life is a Story Problem LLC. January 8, 2015. Buy the book
More Information
- McAdams, David E.. Common. allmathwords.org. Life is a Story Problem LLC. 3/12/2009. http://www.allmathwords.org/en/c/common.html.
- Euclid of Alexandria. Elements. Clark University. 9/6/2018. https://mathcs.clarku.edu/~djoyce/elements/elements.html.
Cite this article as:
McAdams, David E. Greatest Common Factor. 12/21/2018. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/g/greatestcommonfactor.html.
Image Credits
Revision History
12/21/2018: Reviewed and corrected IPA pronunication. (McAdams, David E.)
8/7/2018: Changed vocabulary links to WORDLINK format. (McAdams, David E.)
7/10/2018: Removed broken links, updated license, implemented new markup, implemented new Geogebra protocol. (McAdams, David E.)
1/3/2011: Added highest common factor, highest common divisor and abbreviations. (McAdams, David E.)
2/8/2010: Added "References". (McAdams, David E.)
8/7/2008: Added Understanding Check. (McAdams, David E.)
8/5/2008: Added How To. (McAdams, David E.)
6/7/2008: Corrected spelling. (McAdams, David E.)
7/12/2007: Initial version. (McAdams, David E.)