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: it is 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, follow the following steps:

1. Find the prime factors of all the numbers in your set. For instance, if we seek the GCD of 40 and 60, then their prime factors are 2 and 5 (for 40) and 2, 3, 5 (for 60).

2. For every prime number dividing all the numbers in your set, find its largest power that divides all the numbers in your set. In our case, the only prime factors dividing both 40 and 60 are 2 and 5. The largest power of 2 dividing both 40 and 60 is 4 = 2², while the largest power of 5 dividing 40 and 60 is 5 itself.

3. Multiply these prime powers together to get the GCD. In our case, this will be 20 = 4 × 5. If our numbers have no common prime divisors (i.e., they are coprime/relatively prime), then the GCD is 1.

Via this method it is easy to see 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. Suppose you want to find the GCD of two natural numbers $x$ and $y$ and suppose that $x$ is no greater than $y$.

1. Start by subtracting the smaller number $x$ from the larger $y$.

2. Substitute the larger number $y$ with the result $y-x$, so that you know consider the pair $x, y-x$ instead of $x, y$.

3. Repeat step 1, subtracting the smaller of $x, y-x$ from the larger one. Depending on the original choice of numbers, you may have to subtract either the same number $x$ again or the new number $y-x$.

4. Substitute the larger number with the result.

5. Repeat the algorithm until you reach two equal numbers: this is the GCD.

For instance, starting with 60 and 40, we first subtract 60 - 40 to get 20 and then replace 60 with 20. This gives us the pair 40 and 20. Subtracting 20 from 40, we get 20, with which we then replace 40. This leaves us with two same numbers, 20 and 20, and this is precisely the GCD of 40 and 60.

Modified Euclidean algorithm

The Euclidean algorithm using subtraction can become pretty lengthy (in particular, if the two numbers differ 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. The GCD is then the smaller of the two numbers from the previous step.

For our previous example of 60 and 40, the modified Euclidean algorithm will not differ much from its original version, so we instead consider a different example: 60 and 9:

1. 60 is congruent to 6 modulo 9, and so we replace 60 with 6. Thus, our new pair is 9 and 6.

   (If we wanted to reach this step using the original Euclidean algorithm, we would have to subtract 9 from 60 six times before we would reach the pair 60 and 9. With the modified Euclidean algorithm, we simplify it to one calculation.)

2. 9 is congruent to 3 modulo 6. We thus replace 9 with 3, giving us the pair 6 and 3.

3. Now, 6 is congruent to 0 mod 3, and so following the last step of the algorithm, we take the GCD to be 3, the smaller of the two numbers 6, 3 from the last step.

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 division. 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 only 1 divides all the numbers.

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

For instance, suppose we want to compute the GCD of 60 and 40 again:

1. 2 divides both numbers, so we divide out 60/2 = 30 and 40/2 = 20.
2. 2 divides both 30 and 20, so 30/2 = 15 and 20/2 = 10.
3. Neither 2 nor 3 divides 15 and 10, but the next prime factor 5 does, so we divide 15/5 = 3 and 10/5 = 2.
4. 3 and 2 are coprime (i.e., they have no common factors other than 1), and so we halt. The GCD is the product of divisors used in the previous steps: 2 × 2 × 5 = 20.

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 iteratively 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.

Greatest common divisors are very useful in real life: here is one reason why. Suppose that you want to cover a rectangular wall with square tiles without breaking any tiles. How big can the tiles be? If the wall has dimensions $a \times b$, then the side length $c$ of your tile has to divide both the lengths; otherwise, the tiles will not fit.

In other words, $c$ has to be a common divisor of both $a$ and $b$. The largest admissible side length of your tile is, therefore, $\rm{GCD}(A,B)$. So, if you want to decorate your bathroom walls, better know how to calculate the greatest common factor!

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.