Omni Calculator logo

Greatest Common Denominator Calculator

Created by Davide Borchia
Reviewed by Komal Rafay
Last updated: Jan 18, 2024


With Omni's greatest common denominator calculator, you will learn how to find the greatest number that divides exactly all the numbers in a set. Keep reading this short article to find out:

  • What is the greatest common denominator;
  • How to calculate the greatest common denominator;
  • The properties of the greatest common denominator;

and much more!

What is the greatest common denominator?

The greatest common denominator is a number defined for any possible set of integers (a requirement of the definition of the greatest common denominator) that exactly divides each set member.

In other words, the greatest common denominator is the greatest division shared by all the numbers of a set.

We make extensive use of the GCD in mathematics. Number theory, in particular, uses the concept to describe periodic patterns. In more practical terms, the GCD can be used when looking for exact tessellations or matching figures of different lengths.

However, the most common use of the GCD is almost unnoticed: the reduction of fractions. When you find the simplest form of a fraction, you divide both the numerator and the denominator by the GCD.

Now that you know where we use it, we can learn how to calculate the greatest common denominator.

How to calculate the greatest common denominator

For small numbers finding the greatest common denominator is almost intuitive: look at this set:

{6,12,9}\{6,12,9\}

Clearly, the GCD is 33! But what do we do when the numbers start to grow?

Prime factorization

The GCD is ready to be found if you write the prime factorization of the numbers in a set. The prime factorization is the set of prime numbers elevated to specific exponents that, multiplied, returns the original number. The GCD is the largest shared prime factor, elevated to the highest possible exponent. Take this set: {360,378,405}\{360,378,405\}. The prime factorizations of these numbers are:

360=23325378=2337405=345\begin{split} 360 &= 2^3\cdot3^2\cdot5\\ 378 &= 2\cdot3^3\cdot7\\ 405 &= 3^4\cdot5 \end{split}

Find the repeated prime factor: only 33 appears in all three numbers, and the highest exponent is 22: 323^2 is the GCD of the set!

🙋 Finding the prime factorization is not always a simple task: to simplify your calculations, you can use our prime factorization calculator!

Euclidean algorithm

The GCD of two numbers also divides exactly their difference. It may sound strange, but think about it: the result of the division of the largest number by the GCD can be seen as the sum of two numbers: one of them, multiplied by the GCD, returns the smaller number, the other the difference.

To find the GCD, find the result of the subtraction of the two numbers, and substitute it with the largest number. Proceed until the two numbers match: the result is the GCD. Take, for example, the set {49,14}\lbrace49,14\rbrace. Follow these steps:

  1. Subtract 1414 from 4949: 4914=3549-14 = 35.
  2. Substitute 4545 with 3535.
  3. Subtract 1414 from 3535: 3514=2135-14 = 21.
  4. Substitute 3535 with 2121.
  5. Subtract 1414 from 2121: 2114=721-14 = 7.
  6. Substitute 2121 with 77.
  7. Subtract 77 from 1414: 147=714-7 = 7.

You are left with two 77s: this is your GCD.

To find the GCD of more than two numbers with this method, simply find the GCD of two pairs of numbers (e.g., if the set is {a,b,c}\{a,b,c\}, take GCD(a,b)\mathrm{GCD}(a,b) and GCD(b,c)\mathrm{GCD}(b,c)). Once you find the GCDs, find in turn their GCD in the same fashion: once you are left with two numbers, the result is the greatest common denominator of the whole set of numbers.

Modified Euclidean algorithm

To speed up things, you can use the remainder of the division between the two numbers of which you are calculating the greatest common denominator and use this result in the Euclidean algorithm. For example, in the set {a,b}\{a,b\}, replace the larger number (aa) with amod ba\mod\ b. Repeat the operation, but this time with bb and the result of the previous step. At one point, you will find yourself calculating dmod0d\mod 0: dd is the GCD of the numbers in the set.

How to use our greatest common denominator calculator

Our greatest common denominator calculator works with integer numbers, even negative ones. Input as many as 15 numbers, and see the GCD in the blink of an eye. You can also decide to visualize the steps of the process: in the opposite selection, you will find more methods we didn't analyze in the text but that are as good, if not better than the one presented.

We talked about GCD and other number theory concepts in many other tools. Visit:.

FAQ

How do I calculate the GCD of {12,27,9} with Euclidean algorithm?

To find the GCD of {12,27,9} using the Euclidean algorithm, follow these easy steps:

  1. Find the GCD of 12 and 27 using the Euclidean algorithm:

    • Subtract 12 from 27, and substitute 27 with the result: 27 - 12 = 15.

    • Repeat the step for 12 and 15: 15 - 12 = 3.

    • Repeat the same steps. You will eventually find 3.

    • 3 is the GCD of 12 and 27.

  2. Find the GCD of 27 and 9: GCD(27,9) = 9.

  3. Find the GCD of the results of steps 1. and 2.: GCD(3,9) = 3. This is the GCD of {12,27,9}.

How do I find the GCD using the prime factorization?

To find the GCD using the prime factorization, you must follow a couple of straightforward steps:

  1. Find the prime factorization of the numbers you are analyzing.
  2. Find, if present, the largest shared prime factor.
    • If you can't find it, the GCD is 1.
  3. Find the highest exponent to which the factor found in step 2. is elevated.
  4. The result of the factor elevated to the exponent is the GCD of the given set of numbers.

Can I find the GCD of negative numbers?

Yes: you can find the GCD of negative numbers. The sign doesn't matter; you can easily exclude it from the calculations. The GCD will always be positive, as we assume that the original number comes from the multiplication of the greatest common divisor by a negative number.

Davide Borchia
Data (You may enter up to 15 integer numbers)
#1
#2
Step by step solution?
Choose method:
None
Check out 75 similar arithmetic calculators ➗
Absolute changeAbsolute valueAdding and subtracting fractions… 72 more
People also viewed…

Bilinear interpolation

The bilinear interpolation calculator helps you estimate the value of an unknown function based on the method of bilinear interpolation.

Black hole collision

The Black Hole Collision Calculator lets you see the effects of a black hole collision, as well as revealing some of the mysteries of black holes, come on in and enjoy!

Meat footprint

Check out the impact meat has on the environment and your health.

XOR

The XOR calculator allows you to perform bitwise XOR operations on two numbers.
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service