Greatest Common Denominator Calculator

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!

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.

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

Clearly, the GCD is $3$! 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\}$. The prime factorizations of these numbers are:

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

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 $\lbrace49,14\rbrace$. Follow these steps:

1. Subtract $14$ from $49$: $49-14 = 35$.
2. Substitute $45$ with $35$.
3. Subtract $14$ from $35$: $35-14 = 21$.
4. Substitute $35$ with $21$.
5. Subtract $14$ from $21$: $21-14 = 7$.
6. Substitute $21$ with $7$.
7. Subtract $7$ from $14$: $14-7 = 7$.

You are left with two $7$s: 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\}$, take $\mathrm{GCD}(a,b)$ and $\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\}$, replace the larger number ($a$) with $a\mod\ b$. Repeat the operation, but this time with $b$ and the result of the previous step. At one point, you will find yourself calculating $d\mod 0$: $d$ is the GCD of the numbers in the set.

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

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

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

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.

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.