Greatest Common Divisor - GCD

The Greatest Common Divisor (GCD) refers to the greatest number that is a common divisor for a given set of numbers. 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.

GCD Meaning - GCD Full Form

The meaning and full form of GCD is the Greatest Common Divisor. So, GCD is the greatest positive number which is a common divisor for a given set of positive numbers.

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

GCD of Two Numbers

Let us see the steps given below to learn how to find the GCD of two numbers.

• Step 1: Write the divisors of the number 'a'.
• Step 2: Write the divisors of the number 'b'.
• Step 3: List the common divisors of 'a' and 'b'.
• Step 4: Now find the divisor which is the highest among the common divisors.

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

Divisors of 13 = 1, and 13.
Divisors of 48 = 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.

Therefore, 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:

How to Calculate the GCD using LCM?

Let us see how to calculate the GCD of (a, b) using the LCM method:

• 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 of the numbers by the LCM of the numbers.
• 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 follows:

• The product of 15 and 70 is given as, 15 × 70
• The LCM of (15, 70) is 210.
• We know that GCD (a, b) = (a × b)/ LCM of a and b
• GCD (15, 70) = (15 × 70)/ 210 = 5.

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

☛Related Links

• 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 is GCD in Maths?

The greatest common divisor for any two positive numbers (a, b) is the greatest factor that is common to both the numbers a and b. It is also known as the Highest Common Factor (HCF) or Greatest Common Factor (GCF) of the given numbers.

How to find the GCD of Two Numbers?

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

• Step 1: Find the divisors of the positive number 'a'.
• Step 2: Find the divisors of the positive number 'b'.
• Step 3: List the divisors common to 'a' and 'b'.
• Step 4: Find the divisor which is the highest of all the common divisors of 'a' and 'b'. This is the GCD of 2 numbers.

What is LCM Method for Greatest Common Divisor?

We can find the greatest common divisor of two numbers using the LCM method. As per the LCM method, we can obtain the GCD of any two numbers by finding the product of both the numbers and the least common multiple of both the numbers. The formula which is used to find the GCD is as follows: 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) by the LCM method using the following steps:

• Step 1: Find the product of a and b.
• Step 2: Now, find the least common multiple (LCM) of a and b.
• Step 3: Divide the product of 'a' and 'b' by the LCM of a and b
• Step 4: The obtained value after division is the greatest common divisor (GCD) 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. The value of GCD and HCF can be calculated by checking the common divisors or factors and then finding the greatest divisor of both the numbers.

What is the GCD Formula?

The GCD formula is the formula that is used to find the GCD of two numbers using the LCM of the two numbers. The GCD formula is expressed as, GCD (a, b) = (a × b)/ LCM (a, b). This means if we know the two numbers and their LCM, we can easily find their GCD using this formula.