GCD Calculator

In Maths, the Greatest Common Divisor (GCD) is defined as the largest positive integer that divides each of the integers evenly with the remainder zero. The greatest common divisor is also called the Greatest common denominator(GCD) or Highest Common Factor (HCF). We can denote the greatest common divisor of two integers a and b as GCD(a,b).

How to Find the Greatest Common Divisor or Denominator(GCD)?

Calculating the GCD of numbers can be tricky manually. But there are various techniques that determine the Greatest Common Divisor of given numbers easily by hand. Here, we have taken the most commonly used & standard methods to solve the GCD of numbers, and also you can learn the concept by the provided detailed procedure & show work.

You can select any of the methods that fit to solve the given numbers and find out the Greatest common divisor quickly & easily. Take a look at the methods that you can use to solve GCD here with a detailed explanation & solved examples.

• List of Factors Method
• Prime Factorization
• GCD Formula

Procedure to Solve GCD of Numbers using the List of Factors method

• To find the greatest common divisor of numbers firstly, you have to find the divisors for each number.
• List the common divisor among the divisors obtained.
• However, GCD is the largest number so find the largest common divisor from the list and we get the greatest common divisor.

Example:

Find the GCD of 48, 36, and 124 using a list of factors method?

Solution:

Given numbers are 48, 36, 124

• factors of 48 are 1 , 2 , 3 , 4 , 6 , 8 , 12 , 16 , 24 , 48
• factors of 36 are 1 , 2 , 3 , 4 , 6 , 6 , 9 , 12 , 18 , 36
• factors of 124 are 1 , 2 , 4 , 31 , 62 , 124

The common divisor from each set of factors is 1, 2, 4 and we see that the largest divisor is 4.

Thus, the Greatest Common Divisor of 48, 36, 124 is 4.

Steps to Solve Greatest Common Denominator or Divisor using Prime Factorization

Greatest common divisors can be calculated by determining the prime factorizations of the given numbers. Yes, prime factor decomposition is the most commonly used method to compute the GCD of given numbers. The steps comprised in computing the Greatest common divisor using prime factorization are as follows:

• First and foremost, compute & list out the Prime Factors of each given number separately.
• Pick the common prime factor and product them to get the Greatest Common Divisor.

Example:

Solve the GCD of 16, 88, 104 by prime decomposition?

Solution:

Given numbers are 16, 88, 104

Prime factors of 16 = 2 × 2 × 2 × 2

Prime factors of 88 = 2 × 2 × 2 × 11

Prime factors of 104 = 2 × 2 × 2 × 13

Now product the common prime factor and get the greatest common divisor

Thus, GCF(16, 88, 104) = 2 × 2 × 2 = 8.

How to Calculate GCD of two numbers by GCD Formula?

One more prominent method to calculate the GCD is by using the GCD formula. If a and b are both nonzero, the greatest common divisor of a and b can be calculated with the help of the least common multiple (lcm) of a and b:

GCD(a,b) = a×b / LCM(a,b)

Steps to solve Greatest Common Divisor Using GCD formula:

• Consider the given integers and apply them in the GCD formula.
• Calculate the LCM of given numbers at first, then continue with the GCD calculations.
• Here, you can calculate LCM of given numbers easily by visiting the LCM of two Numbers Calculator
• After finding the LCM of given numbers, substitute the Least common multiple in the GCD formula
• Next, product the given numbers and take the result to divide the LCM of two numbers.
• After the final computation, you will get the GCF of two numbers.

Example:

Find GCD of 23 and 45 using formula?

Solution:

Given numbers are 23 and 45

The formula to find the greatest common divisor of two numbers is

GCD(a, b) = a x b / LCM(a, b)

GCD(23, 45) = 23*45 / LCM(23, 45)

GCD(23, 45) = 1035 / LCM(23, 45)

we get LCM of 23 and 45 is 1035 by applying primes

Now apply LCM(23, 45) in the formula and we get GCD of 23 and 45

GCD(23, 45) = 1035 / 1035

GCD(23, 45) = 1

Therefore, the greatest common divisor or greatest common denominator of 23 and 45 is 1.

What is HCF?

In mathematical terms, Greatest Common Divisor is known as GCD & HCF is Highest Common Factor. For a given set of numbers, the highest factor among the factors of these numbers is called the HCF of these numbers. As these given sets of numbers are perfectly divisible by this factor, it is also called the Greatest Common Divisor.

Know About GCD and Co-prime Numbers

If the two or more integers, of which we want to find the GCD, did not have any common factors other than 1, then that set of numbers are called co-prime numbers. & GCD of co-prime numbers is always 1, as these numbers did not have any other common factors.

Greatest Common Divisor Calculation With Steps

Here we will see the steps to find the Greatest Common Divisor using the prime factorization method:

1. First check the numbers whose GCD we have to find.
2. Take each number & write down the prime factors of that number.
3. Check the list of prime factors of all numbers.
4. Write down the common prime factors from the factorization of a given set of numbers.
5. Multiply these factors to find the GCD of a given set of numbers.

Find The Greatest Common Divisor Solved Example

Example: 

Find the Greatest Common Divisor between the numbers 112, 196 & 84.

Solution:

Here, we have to find the GCD of 112, 196 & 84.

So, let us find the prime factors of these numbers one by one.

112 = 2 × 2 × 2 × 2 × 7

196 = 2 × 2 × 7 × 7

84 = 2 × 2 × 3 × 7

Here, the common prime factors of the above numbers are 2, 2, 7

So, we have to multiply these factors to get the GCD.

Hence, GCD (84, 112, 196) = 2 × 2 × 7 = 28.

Use several LCM and HCF Calculators at hcflcm.com and understand the topics without having any doubts.

FAQs on Find The Greatest Common Divisor Calculator

• What is the GCD of 4 and 4?

4 is the greatest common factor of 4 and 4.

• What is the greatest common factor of 24 32 and 36?

Since 4 is the largest integer dividing 24,32 and 36 hence it is the greatest common factor of the given numbers.

• How do you find the GCD of 5 numbers?

To calculate the GCD of 5 numbers the first step is to list the factors of the 5 numbers and then determine the largest common factor shared by all the numbers.

• How do you find the GCD of two large numbers?

First, break the two numbers into their prime factorization, and now identify those factors which both the numbers have in common. Now multiply these together to get the answer.