Greatest Common Divisor (GCD): Definition, Methods,  Examples

What Is the Greatest Common Divisor (GCD)?

The greatest common divisor (GCD), also known as “greatest common factor (GCF)” or “highest common factor (HCF)”, of two numbers is the greatest factor that divides both the numbers. In simple words, it is the largest factor shared between two or more numbers. 

Definition of Greatest Common Divisor

The greatest common divisor (GCD) of two integers can be defined as the largest positive integer that is a divisor of both numbers. It is also called the highest common factor (HCF) or the greatest common factor (GCF). 

The GCD of two numbers a and b is sometimes written as GCD(a, b) or gcd(a, b).

For example, the GCD of 8 and 12 is 4. 

GCD$(8, 12) = 4$

What Are Factors?

A factor of a number is a number that divides the given number evenly without leaving a remainder. Factors are numbers that you can multiply together to get another number, called the product. Every number has at least two factors.

Example 1: $2 \times 4 = 8$.

So, 2 and 4 are both factors of 8.

Example 2: We can write 12 as 

$12 = 1 \times 12$

$12 = 2 \times 6$

$12 = 3 \times 4$

Therefore 1, 2, 3, 4, 6, and 12 are all factors of 12. 

What Are Common Factors?

As the name implies, a common factor is a factor common between two or more numbers. In other words, it is a number that can evenly divide a set of two or more numbers.

We can find the common factors of two or more numbers by listing the factors of each number and then identify the factors that are common among them. 

Example 1: Find the common factors of 15 and 20.

Factors of $15 = 1, 3, 5, 15$

Factors of $20 = 1, 2, 4, 5, 10, 20$

Factors common in 15 and 20 are 1 and 5.

Example 2: Find common factors of 16 and 24.

Factors of $16 = 1, 2, 4, 8, 16$

Factors of $24 = 1, 2, 3, 4, 6, 8, 12, 24$

Common factors of 16 and $24 = 1, 2, 4, 8$

How to Find the GCD (Greatest Common Divisor)

In order to determine the greatest common divisor for a pair of two positive integers (m, n), follow the steps listed below:

Step 1: Write the factors of the positive integer “m.”

Step 2: Write the factors of the positive integer “n.”

Step 3: Identify the common divisors of “m” and “n.”

Step 4: Find the divisor that is the largest among the common divisors of “m” and “n.”

Methods to Find the Greatest Common Divisor

There are numerous ways to determine the biggest common divisor of two numbers. The methods to find G.C.D. are as follows.

1. Listing method

2. Prime factorization method

3. Long division method

4. Repeated division method

5. Euclid’s division algorithm

GCD by Listing Method

In this method, we list the factors of the given numbers and then highlight the common factors. After identifying the common factors, we find the largest common factor.

Example: Find the GCD of 24 and 30 using the listing method.

Factors of $24 =  1, 2, 3, 4, 6, 8, 12, 24$

Factors of $30 = 1, 2, 3, 5, 6, 10, 15, 30$

Common factors of 24 and $30 = 1, 2, 3, 6$

G.C.D. of 24 and $30 = 6$

GCD by Prime Factorisation Method

In this method, we find the prime factorization of the given numbers using the factor tree method or division method. Using the prime factorization, find the common factors between the two numbers. Multiply these together to find the greatest common divisor. This method is applicable only for positive integers.

Example 1: Find the greatest common divisor of 24 and 30.

Let’s find the prime factorization of 24 and 30 using the factor tree method.

Prime factors of $24 = 2 \times 2 \times 3$

Prime factors of $36 = 2 \times 2 \times 3 \times 3$

Common factors of 24 and $36 = 2, 2, 3$

G.C.D. of 24 and $36 =  2 \times 2 \times 3 = 12$

Example 2:  Find the greatest common factor of 168 and 180.

Solution: 

Prime factors of $160 = 2^{3} \times 3 \times 7 = 2 \times 2 \times 2 \times 3 \times 7$

Prime factors of $180 = 2^{2}\times 3^{2} \times 5 = 2 \times 2\times 3 \times 3 \times 5$

The common factors are $2 \times 2 \times 3 = 12$

Therefore, greatest common factor of $(168, 180) = 12$

GCD by Long Division Method

The long division method is more useful for finding GCD of large numbers. The steps to be followed for long division method are as follows: 

Step 1: Divide the large number by the smaller one. 

Step 2: Treat the remainder obtained as the new divisor and set the previous divisor as the new dividend.

Step 3: Divide the first divisor by the first remainder.

Step 4: Divide the second divisor by the second remainder.

Step 5: Continue this process till the remainder becomes 0.

Step 6: The divisor, which does not leave a remainder, is the G.C.D. of the two numbers and thus, the last divisor is the required G.C.D. of the given numbers.

Example 1: Find GCD of 105 and 189 using the long division method. 

Since the last divisor that we got is 21, we can say that the greatest common divisor of 105 and 189 is 21.

G.C.D. of 105 and $189 = 21$.

Example 2: Find GCD of 32, 56, and 46.

To find the GCD of three numbers, we start by using the long division on any two numbers. Once the division is complete, we divide the remaining number by the last divisor obtained in the first division.

GCD by Repeated Division Method

This method is pretty similar to the long division method. Let’s understand the steps.

Step 1: Divide the given numbers by the smallest common prime factor.

Step 2: Divide the quotients thus obtained by their smallest common prime factor.

Step 3: Repeat until there is no more common prime factor between the quotients. 

Step 4: Multiply all the divisors (prime factors).

Example: Find the G.C.D. of 24 and 36 using repeated division.

GCD by Euclid’s Division Algorithm

This method is applicable only for positive integers. Euclid’s division algorithm is based on the Euclid’s division lemma. It is a method used to find GCD of two positive integers.

According to Euclid’s division lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation $a = bq + r$, where $0 \le r \lt b$. 

Using this lemma, we express the larger number “a” in terms of the smaller number “b” in the quotient remainder form $a = b q + r$. 

If $r = 0$, then b is the G.C.D. of a and b. 

If r 0, then we again use the lemma on the numbers b and r as GCD (b, r) $=$ GCD (a, b).

Repeat the above process until the remainder is zero. When the remainder is zero, the last divisor is the GCD of given numbers. (OR the last non-zero remainder is the GCD.)

• If $a = 0$, then GCD $(a, b) = b$

GCD $(0, b) = b$.

• If $b = 0$, then GCD $(a, b) = a$

GCD $(a, 0) = a$.

Example 1: Find the G.C.D. of 123 and 36.

Example 2: Find the G.C.D. of 1180 and 482.

Thus, gcd$(1180, 482) = 2$

Greatest Common Divisor Formula

If a and b are positive integers, then the greatest common divisor of a and b can be given by:

 GCD $(a,b) = \frac{a \times b}{LCM (a, b)}$

Finding Greatest Common Divisor by LCM Method

The greatest common factor can be found using the LCM method using the following formula:

The steps to calculate the GCD of (a, b) using the LCM method is:

Step 1: Find the product of a and b.

Step 2: Find the least common multiple (LCM) of a and b.

Step 3: Divide the product by LCM.

Step 4: The obtained value is the greatest common divisor of (a, b).

Example: If the LCM(24, 36) = 72, find the GCD(24, 36).

GCD $(a, b) = \frac{a \times b}{LCM (a, b)}$

GCD $(24, 36) = \frac{24 \times 36}{LCM (24, 36)}= \frac{24 \times 36}{72} = 12$

Applications of Greatest Common Divisor

1. To simplify fractions or ratios, to reduce them to their simplest form.

Example: To find the simplest form of $\frac{35}{50}$, we find the gcd(35, 50).  

GCD$(35,50) = 5$

Divide both the numerator and denominator by the gcd.

$\frac{35 \div 5}{50 \div 5} = \frac{7}{10}$

2. To find the LCM of the given numbers.

LCM $(a, b) = \frac{a \times b}{GCD(a, b)}$

3. The concept of GCD is used in many real-life situations, such as dividing a group of people into smaller sections, arranging students in rows and columns of equal numbers.
   
4. GCD has interesting applications in geometry as well. For example, we can determine the side of the largest square tile that can cover the rectangular floor of dimensions “a b” by finding the GCD(a,b).

Facts about Greatest Common Divisor

Conclusion

In this article, we have learned about the greatest common divisors and methods of finding them. Let us solve some greatest common divisor examples using those methods.

Solved Examples on the Greatest Common Divisor

1. Find GCD of 16 and 60 using the long division method. 

Since last divisor is 4, GCD of 16 and 60 = 4

2. Find the greatest common factor of 150 and 180 by using the prime factorization method.

Solution: 

Prime factors of $150 = 2 \times 3 \times 5^{2} = 2 \times 3 \times 5 \times 5$

Prime factors of $180 = 2^{2}\times 3^{2}\times 5 = 2 \times 2 \times 3 \times 3 \times 5$

The common factors $= 2, 3, 5$

GCD $(150, 180) = 2 \times 3 \times 5 = 30$

Therefore, greatest common factor of $(150, 180) = 30$

3. If the LCM of 15 and 70 is 210, find the greatest common divisor of 15 and 70.

Solution: 

$a = 15 , b = 70$

The greatest common divisor of 15 and 70 can be calculated using the given formula:

GCD $(a,b) = \frac{a \times b}{LCM (a, b)}$

Thus, GCD $(a,b) = \frac{15 \times 70}{210} =  5$

Therefore, the greatest common divisor of (15, 70) is 5.

Practice Problems on the Greatest Common Divisor

Frequently Asked Questions about Greatest Common Divisor