Greatest Common Divisor - GCD

The greatest common divisor (GCD) refers to the greatest positive integer that is a common divisor for a given set of positive integers. It is also termed as the highest common factor (HCF) or the greatest common factor (GCF). In this lesson, we will learn how to find the greatest common divisor in detail.

For a set of positive integers (a, b), the greatest common divisor is defined as the greatest positive number which is a common factor of both the positive integers (a, b). GCD of any two numbers is never negative or 0 as the least positive integer common to any two numbers is always 1. There are two ways to determine the greatest common divisor of two numbers:

• By finding the common divisors
• By Euclid's algorithm

For a set of two positive integers (a, b) we use the below-given steps to find the greatest common divisor:

• Step 1: Write the divisors of positive integer "a".
• Step 2: Write the divisors of positive integer "b".
• Step 3: Enlist the common divisors of "a" and "b".
• Step 4: Now find the divisor which is the highest of both "a" and "b".

Example: Find the greatest common divisor of 13 and 48.
Solution: We will use the below steps to determine the greatest common divisor of (13, 48).

Divisors of 13 are 1, and 13.
Divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48.

The common divisor of 13 and 48 is 1.
The greatest common divisor of 13 and 48 is 1.

Thus, GCD(13, 48) = 1.

As per the LCM Method for the greatest common divisor, the GCD of two positive integers (a, b) can be calculated by 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 values obtained in Step 1 and Step 2.
• Step 4: The obtained value after division is the greatest common divisor of (a, b).

Example: Find the greatest common divisor of 15 and 70 using the LCM method.
Solution: The greatest common divisor of 15 and 70 can be calculated as:

• The product of 15 and 70 is given as, 15 × 70
• The LCM of (15, 70) is 210.
• GCD (15, 20) = (15 × 70)/ 210 = 5.

∴ The greatest common divisor of (15, 70) is 5.

As per Euclid's algorithm for the greatest common divisor, the GCD of two positive integers (a, b) can be calculated as:

• If a = 0, then GCD (a, b) = b as GCD (0, b) = b.
• If b = 0, then GCD (a, b) = a as GCD (a, 0) = a.
• If both a≠0 and b≠0, we write 'a' in quotient remainder form (a = b×q + r) where q is the quotient and r is the remainder, and a>b.
• Find the GCD (b, r) as GCD (b, r) = GCD (a, b)
• We repeat this process until we get the remainder as 0.

Example: Find the GCD of 12 and 10 using Euclid's Algorithm.
Solution: The GCD of 12 and 10 can be found using the below steps:
a = 12 and b = 10
a≠0 and b≠0
In quotient remainder form we can write 12 = 10 × 1 + 2
Thus, GCD (10, 2) is to be found, as GCD(12, 10) = GCD (10, 2)

Now, a = 10 and b = 2
a≠0 and b≠0
In quotient remainder form we can write 10 = 2 × 5 + 0
Thus, GCD (2,0) is to be found, as GCD(10, 2) = GCD (2, 0)

Now, a = 2 and b = 0
a≠0 and b=0
Thus, GCD (2,0) = 2

GCD (12, 10) = GCD (10, 2) = GCD (2, 0) = 2

Thus, GCD of 12 and 10 is 2.

Euclid's algorithm is very useful to find GCD of larger numbers, as in this we can easily break down numbers into smaller numbers to find the greatest common divisor.

Topics Related to Greatest Common Divisor

Check out these interesting articles to know more about the greatest common divisor (GCD) and its related topics.

• Common Denominator
• What is the lowest common denominator of 8 and 9?
• Numerator and Denominator Calculator
• Common Denominator Calculator
• Least Common Denominator Worksheets
• Rationalize the Denominator

What does Greatest Common Divisor Mean?

The greatest common divisor for any two positive integers (a, b) is the greatest factor which is common to both the integers a and b. It is also known as the highest common factor or greatest common factor.

How do you find the Greatest Common Divisor of Two Numbers?

The greatest common divisor of two numbers can be determined using the following steps:

• Step 1: Find the divisors of positive integer "a".
• Step 2: Find the divisors of positive integer "b".
• Step 3: Lis the divisors common to "a" and "b".
• Step 4: Find the divisor which is the highest of all the common divisors of both "a" and "b".

What is LCM Method for Greatest Common Divisor?

We can determine the value of the greatest common divisor by using the LCM method. As per the LCM method, we can obtain the GCD of any two positive integers by finding the product of both the numbers and the least common multiple of both numbers. LCM method to obtain the greatest common divisor is given as GCD (a, b) = (a × b)/ LCM (a, b).

How to Find the Greatest Common Divisor Using LCM Method?

We can find the GCD of (a, b) using the LCM method by using the following steps:

• Step 1: Determine the product of a and b.
• Step 2: Now, find the least common multiple (LCM) of a and b.
• Step 3: Divide the values obtained in Step 1 and Step 2.
• Step 4: The obtained value after division is the greatest common divisor of (a, b).

Can the Greatest Common Divisor be Negative?

No, the greatest common divisor cannot be negative as it represents the greatest common divisor of two positive integers. The least value of GCD can be 1 and not lesser than it. This proves the point that GCD cannot hold a negative value.

Are GCD and HCF the Same?

Yes, GCD and HCF are the same. In either case, the value of GCD, HCF can be determined by checking the common divisors or factors and then finding the greatest divisor of both the numbers.