Sales Toll Free No: 1-855-666-7446

Greatest Common Divisor

Top

A largest positive integer which divides two or more integers without any remainder is called Greatest Common Divisor or Greatest Common Factor.
It is also known as highest common factor or greatest common measure. Greatest common divisor is abbreviated as GCD. 1 is considered as the common factor if there is no common factor.
Commonly used methods to find the greatest common factor are :

1) Prime factor method and
2) successive division method.
Example of greatest common divisor:  Consider 6 and 15.
Factors of 6 are 1, 2, 3, 6
Factors of 15 are 1, 3, 5,15
From above, we see that 1 and 3 are the common factors. And 3 is the largest of the common factors. So GCD of 6 and 15 is 3.

Greatest Common Divisor Definition

Back to Top
Greatest common divisor of two or more numbers is the greatest number among all their common factors. It can also be done by listing the factors. It is the largest number that gives zero remainder, when dividing the given numbers separately.
GCD is the largest positive integer that divides completely given numbers. For example, the GCD of 12 and 30 is 6.

How to Find Greatest Common Divisor?

Back to Top
There are different methods to find the greatest common divisor. Steps for common division method, prime factorization and listing factor are explained in very simple steps.

Common Division Method:

1) Divide the greater number by smaller number and find the remainder.
2) Continue this process with the first remainder as divisor and first divisor as dividend.
3) Until we get a zero as remainder carry on the process.
4) Once we get a zero, last divisor is the highest common factor.

Prime factorization :
Express the number in terms of its factors.

1) Find the prime factors of each of the given numbers.
2) Write the common prime factors of the numbers.
3) Multiply all the selected prime factors. The product of the common prime factors is the H.C.F.

Listing factors:

1) Find the factors of all the numbers.
2) Write the factors that are common to all the numbers.
3) Write the highest of the common factors. It is the H.C.F.

Greatest Common Factor Problems

Back to Top
Given below are some problems related to greatest common factor. This will help you in having a clear understanding of the topic:

Example 1 : Find the greatest common factors of 45, 12 and 225.

Solution :
Factors of 45 = 1, 3, 5, 9, 15, 45

Factors of 12 = 1, 2, 3, 4, 6, 12

Factors of 225 = 1, 3, 5, 9, 12, 25, 45, 75, 225

Therefore the common factors of 45, 12 and 225 =  1 and 3.
So for the given problem highest common factor is 3.

Example 2 : Find the H.C.F of 18, 45 and 72?

Solution :
Factors of 18 = 1, 2, 3, 6, 9, 18
45 = 1, 3, 5, 9, 15, 45
72 = 1, 2, 3, 4, 6, 8, 9, 12, 18, 36, 72

Common factors of 18, 45 and 72 are 1, 3, 9
Therefore the highest common factor of 18, 45 and 72 is 9.

Example 3 : What is the greatest common factor of $\frac{12}{30}$?

Solution : First lets find the factor for 12 : 1, 2, 3, 4, 6, 12.

Similarly the factors of 30 are : 1, 2, 3, 5, 6, 10, 15 and 30.

$\Rightarrow$ $\frac{12}{30}$ = $\frac{1, 2, 3, 4, 6, 12}{1, 2, 3, 5, 6, 10, 15, 30}$

From above we can clearly see that the common factors for $\frac{12}{30}$ are 1, 2, 3 and 6.
Therefore the greatest common factor of $\frac{12}{30}$ is 6.