GCD Calculator

Calculating the GCD goes from being a no-brainer to being a painstaking effort. Use our GCD calculator to make all your problems part of the first of these two possibilities. Keep reading our short article to learn:

• What is the greatest common divisor of a set of numbers;
• How to calculate the GCD; and
• Five algorithms to calculate the GCD.

The GCD (short for greater common divisor) is a useful mathematical concept, the largest number that divides exactly all the numbers in a set. The GCD is defined for every number: reals, negatives, etc. However, we meet it most often when dealing with natural numbers.

The GCD has many applications, and in most of them we don't even notice it, but we apply it as we do with many, easier, mathematical operations, for example when we simplify fractions. However, as you will learn, this simple operation has many properties, and it can entertain most mathematicians with various algorithms, more or less complex. Let's discover them!

To calculate the GCD we can use different intuitive methods:

• Prime factorization;
• Euclidean algorithm; and
• Modified Euclidean algorithm.

Let's see them one by one.

Calculate the GCVD using prime factorization

To calculate the GCD with prime factorization, find the prime factors of all numbers of a set, and select the largest common prime factor, choosing as exponent the highest possible that appears in all the factorizations. That's the greater common divisor. This method intuitively tells you that the GCD of a set of prime numbers is $1$.

Calculate the GCD with the Euclidean algorithm

The original Euclidean algorithm for the GCD requires just a bunch of subtractions. The process is simple. Consider a couple of integers for which you want to find the GCD.

1. Start by subtracting the smaller number from the larger one.
2. Substitute the largest number with the result.
3. Repeat step 1, subtracting the smallest number of the pair from the largest number. You may have to subtract the same number again, depending on the original choice of numbers.
4. Substitute the largest number with the result.
5. Rinse and repeat.
6. The algorithm ends when the two numbers are equal: the last result is also the GCD.

Modified Euclidean algorithm

The Euclidean algorithm using subtraction can become pretty lengthy (in particular if the two number differs by much at the beginning). Luckily, we can apply similar reasoning using a different operation: the modulo. In this case, we perform the following steps:

1. We calculate the remainder of the division of the larger number by the smaller one (using the modulo operation).
2. We substitute the larger number with the remainder.
3. We repeat the modulo operation on the new pair of numbers.
4. The algorithm proceeds until the result of the modulo operation is $0$

We can find the GCD in other ways, one more creative and one involving more reasoning.

Upside-down division GCD algorithm

This method is an alternative way to calculate the GCD based solely on divisions. It works wonders in most cases! The procedure is simple:

1. Find the smallest prime number that divides exactly all the numbers in the desired set.
2. Divide all the numbers by these prime factors.
3. Repeat the steps above.
4. The algorithm ends when you can't find a number different than $1$ that divides all the numbers.

To find the GCD, multiply all the divisor.
Note how this is nothing but the prime factorization method, only computed in "real-time" and selecting the factors that divide all the numbers right away.

Binary algorithm for the GCD

The binary algorithm for the GCD uses a clever combination of properties of this operation to find the result without ever computing this quantity directly. The properties used are:

• $\rm{GCD}(0,a) = a$;
• $\rm{GCD}(2\cdot a,2\cdot v)= 2\cdot\rm{GCD}(a,b)$;
• $\rm{GCD}(2\cdot a,b) = \rm{GCD}(a,b)$ if $b$ is odd; and
• $\rm{GCD}(a,b) = \rm{GCD}(|a-b|,\rm{min}(a,b))$ if both $a$ and $b$ are odd.

By tentatively applying these identities, you can reach the first identity and consequently the GCD. However, we must follow an iterative approach to implement the algorithm effectively. You can discover it with our GCD calculator!

To use our GCD calculator simply start inserting the desired numbers in the field at the top of our tool. If you need more numbers, don't worry: the fields will appear!

We will immediately show you the result, so that if you only need quick help with math, you're good to go. However, if you are curious, you can select one of the algorithms we detailed above and see the steps we used to reach the solution.

Calculating the greatest common divisor is a simple mathematical operation, but we can observe it from many different sides. Try them at our related tools:

• The GCF calculator;
• The greatest common denominator calculator;
• The greatest common factor calculator; and
• The greatest common divisor calculator.

The answer is 3. To calculate the greatest common divisor of 12, 45, 21, and 15:

1. Find the prime factorization of all your numbers:
   • 12 = 2² × 3;
   • 45 = 3² × 5;
   • 21 = 3 × 7; and
   • 15 = 3 × 5.
2. Identify the prime factors that appear in all the factorizations. In our case, it's only 3.
3. Choose the highest possible exponent of the factor above that appears in all the factorizations. In our case, it's 1.
4. The GCD is: 3¹ = 3.

To calculate the greatest common divisor of 180 and 210 with the upside-down method, follow these steps:

1. Divide 180 and 210 by the smallest possible prime number that divides them exactly (2):
   • 180/2 = 90;
   • 210/2 = 105.
2. Repeat the step above, but note that now we must divide by 3:
   • 90/3 = 30;
   • 105/3 = 35.
3. This time, do it with 5:
   • 30/5 = 6;
   • 35/5 = 7.
4. The only prime number that divides 6 and 7 is 1.
5. Calculate the GCD by multiplying the divisor mentioned above:
   GCD(180,210) = 2 × 3 × 5= 30.

To calculate the greatest common divisor with the binary algorithm, we use four identities:

• GCD(0,a) = a;
• GCD(2 · a,2 · v)= 2 · GCD(a,b);
• GCD(2 · a,b) = GCD(a,b), if b is odd; and
• GCD(a,b) = GCD(|a-b|,min(a,b)), if both a and b are odd.

Use them iteratively to reduce the problem of finding GCD(a,b) to the first case, with which you can find the desired result.