Greatest Common Factor
In mathematics, the GCF of two or more non-zero integers, x & y, is the greatest positive integer m, which divides both, x & y. The Greatest Common Factor is commonly known as "GCF." Here, "Greatest" can be replaced with "Highest" and "Factor" can be replaced with "Divisor." So "Greatest Common Factor" is also known as:
- Highest Common Divisor (HCD)
- Highest Common Factor (HCF)
- Greatest Common Divisor (GCD)
GCF is used almost all the time with fractions, which are used a lot in everyday life. In order to simplify a fraction or a ratio, you can find the GCF of the denominator and numerator and get the required reduced form. Also, if we look around, the arrangement of something into rows and columns, distribution and grouping, all this require the understanding of GCF. To calculate GCF, there are three common ways- division, multiplication, and prime factorization.
What Is Greatest Common Factor (GCF)?
The GCF (Greatest Common Factor) of two or more numbers is the greatest number among all the common factors of the given numbers. The GCF of two natural numbers x and y is the largest possible number which divides both x and y.
Example: Let us find the greatest common factor of 18 and 27.
First, we list the factors of 18 and 27 and then we find out the common factors.
Factors of 18: 1, 2, 3, 6, 9, 18
Factors of 27: 1, 3, 9, 27
The common factors of 18 and 27 are 1,3 and 9. Among these numbers, 9 is the greatest (largest) number. Thus, the GCF of 18 and 27 is 9. This is written as: GCF(18,27) = 9.
A factor of a number is its divisor as well. Hence the greatest common factor is also called the "Greatest Common Divisor" (or) "GCD." In the above example, the greatest common divisor (GCD) of 18 and 27 is 9 which can be written as: GCD (18,27) = 9.
How to Find Greatest Common Factor(GCF)?
Following are 3 methods for finding the greatest common factor of two numbers.
- Listing Out Common Factors
- Prime Factorization
- Division Method
GCF by Listing Out the Common Factors
In this method, common factors of both the numbers can be listed, it then becomes easy to check for the common factors. By marking the common factors, we can choose the greatest one amongst all of them. Let's look at the example given below:
Example: What is the GCF of 30 and 42?
- Step 1 - List out the factors of each number. Factors of 30 - 1, 2, 3, 5, 6, 10, 15, 30. Factors of 42 - 1, 2, 3, 6, 7, 14, 21, 42
- Step 2 - Mark all the common factors.
- Step 3 - 6 is the common factor and the greatest one.
Therefore, GCF of 30 and 42 = 6.
Finding the greatest common factor by listing factors may be difficult if the numbers are bigger. In such cases, we use the prime factorization and division methods for finding GCF.
GCF by Prime Factorization
Prime factorization is a way of expressing a number as a product of its prime factors, starting from the smallest prime factor of that number. Let's look at the example given below:
Example 1: What is the GCF of 60 and 90?
- Step 1 - Represent the numbers in the prime factored form.
- Step 2 - GCF is the product of the factors that are common to each of the given numbers.
Thus, GCF (60,90) = 21 x 31 x 51 = 30.
Therefore, GCF of 60 and 90 = 30
GCF by Division Method
The division is a method of grouping objects in equal groups, whereas for large numbers we follow long division, which breaks down a division problem into a series of easier steps. The greatest common factor (GCF) of a set of whole numbers is the largest positive integer that divides evenly into all the given numbers, without leaving any remainder. Let's look at the example given below:
Example: Find the GCF of 198 and 360 using the division method.
Among the given two numbers, 360 is the larger number and 198 is the smaller number.
- Step 1 - Divide the larger number by the smaller number using long division.
- Step 2 - If the remainder is 0, then the divisor is the GCF. If the remainder is NOT 0, then make the remainder of the above step as the divisor and the divisor of the above step as the dividend and perform long division again.
- Step 3 - If the remainder is 0, then the divisor of the last division is the GCF. If the remainder is NOT 0, then we have to repeat step 2 until we get the remainder 0.
Therefore, the GCF of the given two numbers is the divisor of the last division. In this case, the divisor of the last division is 18. Therefore, GCF of 198 and 360 is 18.
Greatest Common Factor of Multiple Numbers
We have discussed finding the GCF of two numbers. Now, what if there are more than two numbers. For multiple numbers, listing out common factors becomes difficult. Thus, we can use either of the methods: Prime Factorization or Long Division.
1. To find the GCF of three numbers
For finding the GCF of three numbers, we can use long division as well as prime factorization. In order to find the GCF by long division, the following steps are to be followed:
- First, we will find the GCF of two of the numbers.
- Next, we will find the GCF of the third number and the GCF of the first two numbers.
Example: Find the GCF of 126, 162, and 180.
First, we will find the GCF of the two numbers 126 and 162.
Thus, GCF of 126 and 162 = 18 ........(1)
Next, we will find the GCF of the third number, which is 180, and the above GCF18
Thus, GCF of 180 and 18 =18 ......(2)
From (1) and (2), GCF(198,360) = 18. Therefore, GCF of 198 and 360 = 18
2. To find the GCF of four numbers
For finding the GCF of four numbers, we can use prime factorization as well as the division method. In the prime factorization method, we just take prime factors of the given numbers, specifically prime factors that divide all the given numbers. Let's have a look at the example given below, where prime factorization has been used to find the GCF of four numbers.
Example: Find the GCF of 72, 24, 140, and 42.
2 is the only prime factor which divides 72,140,24 and 42. Thus, GCF (72,140,24,42) = 21 = 2
Therefore, GCF of 72, 24, 140, and 42 is 2.
Difference between GCF and LCM
The GCF or the greatest common factor of two or more numbers is the greatest factor among all the common factors of the given numbers, whereas the LCM or the least common multiple of two or more numbers is the smallest number among all common multiples of the given numbers. The following table shows the difference between GCF and LCM:
|Greatest Common Factor(GCF)||Least Common Multiple(LCM)|
The GCF of two natural numbers a and b is the greatest natural number x, which is a factor of both a and b.
The LCM of two natural numbers a and b is the smallest number y, which is a multiple of both a and b.
In the intersection of the sets of common factors, it is the greatest value.
In the intersection of the sets of multiple, it is the minimum value.
|GCF(a, b) = x||
LCM(a, b) = y
Solved Examples on GCF
Example 1: Find the GCF of 6, 72, and 120 by using the "listing factors" method.
The given numbers are 6, 12, and 36. We will find the factors of each of these numbers. Then, circle the common factors.
In this example, 1, 2, 3, and 6 are all common factors of 6, 12, and 36. Out of all these common factors, 6 is the greatest, and hence, GCF(6,12,36) = 6
Example 2: Find the GCF of 168, 252, and 288 by the "prime factorization method."
The given numbers are 168, 252, and 288. We will find the prime factorization of each of these numbers.
Thus, GCF (168,252,288) = 2 x 2 x 3 = 22 x 31. The GCF of these three numbers will be the product of the prime factors of all three numbers. Thus, GCF of 168, 252 and 288 = 22 x 31 = 12. Therefore, GCF of 168, 252 & 288 is 12.
Example 3: Find the GCF of 9000 and 980 using the "division method."
Among the given numbers, 9000 is the largest, and 980 is the smallest. We will divide the larger number by the smaller number. Next, we will make the remainder as the divisor and the last divisor as the dividend and divide again. We will repeat this process until the remainder is 0.
Therefore, the GCF of 9000 and 980 is 20.
FAQs on GCF
What is a Common Factor?
A common factor of two or more numbers is a factor that is common to both of the given numbers. For example, the common factors of 45 and 25 are 1 and 5.
How to Find the GCF? Give an example.
There are 3 methods to calculate the GCF of two numbers: listing out of the common factors, prime factorization, and division method.
What is the Greatest Common Factor of Two Prime Numbers?
A prime number has only two factors (1 and itself). Hence, two prime numbers cannot have any common factor other than 1. Therefore, the greatest common factor of two prime numbers is 1. For example, the greatest common factor of 5 and 7 is 1.
What is the Greatest Common Factor of 24 and 15?
The factors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. The factors of 15 are 1, 3, 5, and 15. The common factors of 24 and 15 are 1 and 3. Hence, the GCF of 24 and 15 is 3.
What is the GCF of 15 and 20?
The factors of 15 are 1, 3, 5, and 15. The factors of 20 are 1, 2, 4, 5, 10, and 20. The common factors of 15 and 20 are 1 and 5. Thus, the GCF of 15 and 20 is 5.
Are GCF and HCF the Same?
The Greatest Common Factor abbreviated as GCF and is also known as the Highest Common Factor (HCF). So, yes, GCF and HCF are the same.
Is GCF Greater Than LCM?
The LCM is the Least Common Multiple of the given numbers that can be divided by both the numbers, while the GCF is the Greatest Common Factor of the given numbers that divide both the numbers. Thus, for any two numbers, the LCM of the numbers is greater than the GCF of the numbers.