About the calculator
With this calculator you can calculate the greatest common divisor (GCD) of at least 2 numbers. Only numbers greater than 0 are accepted. It can be selected whether the GCD should be calculated with the help of prime factorizations or with the Euclidean algorithm. The greatest common divisor can be used for simplifying fractions.
What is the GCD?
The greatest common divisor of 2 numbers is the largest natural number by which both numbers can be divided without a remainder. For example, 4 is the greatest common divisor of 12 and 16. 2 is also a divisor of 12 and 16, but not the greatest and therefore not the GCD.
GCD with Prime factorizations
Every integer greater than 1 is either itself a prime number or can be represented as a product of primes. The individual numbers of this product are called prime factors.
For example, for the number 156: 2 · 2 · 3 · 13
And for the number 84: 2 · 2 · 3 · 7
To determine the greatest common divisor, the common prime factors must be determined from both prime factorizations and the product is formed from these. It is important that if a number occurs multiple times in both prime factorizations, then it also occurs multiple times in the product.
The common prime factors of 156 and 84 are: 2, 2, 3
Thus the GCD is 2 · 2 · 3 = 12
GCD with Euclidean algorithm
In the Euclidean algorithm, the larger number is first divided by the smaller number with remainder. If the result contains a remainder not equal to 0, the former smaller number (divisor) becomes the new larger number (divident) and the remainder becomes the new smaller number (divisor). This is done until the remainder is 0. The GCD is then the smaller number (divisor) of the last calculation.
Example:
As an example, the greatest common divisor of the numbers 84 and 156 should be calculated again.
In the first step, 156 (the larger number) is divided by 84 (the smaller number) with remainder.
156:84=1R72
The remainder is not yet 0. Therefore, further calculations must be made. Now the 84 is divided by the remainder (i.e. the 72).
84:72=1R12
The remainder is again not equal to 0. So the previous smaller number (72) is again divided by the remainder (12).
72:12=6R0
The remainder is 0. This means that the greatest common divisor was found. The greatest common divisor is from the last calculation step the number by which was divided. So 12.
GCD of more than 2 numbers
But how do you calculate the greatest common divisor of more than 2 numbers?
Prime factorization:
Determining the GCD of more than 3 numbers with the help of prime factorization works exactly the same as with 2 numbers. The prime factors are calculated for each number, the common prime factors are determined and the product of the common prime factors is formed.
Example:
The greatest common divisor of 156, 84 and 90 is to be determined.
Prime factorization of 156: 2 · 2 · 3 · 13
Prime factorization of 84: 2 · 2 · 3 · 7
Prime factorization of 90: 2 · 3 · 3 · 5
The common prime factors are: 2 and 3
Thus applies: gcd(156, 84, 90) = 2 · 3 = 6
Euclidean algorithm:
The Euclidean algorithm always works only with 2 numbers at the same time. What you can do, however, is apply the algorithm to 2 numbers first and then apply the algorithm to the result and the next number. It does not matter in which order you do this.
For example, if you have 3 numbers a, b, and c, you can first calculate gcd(a, b) = z and then calculate gcd(z, c) to get the greatest common divisor of all 3 numbers. But you could also first determine the greatest common divisor of b and c and then use the intermediate result and a to determine the greatest common divisor of all 3 numbers.
It applies:
gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b) = gcd(gcd(b, c), a)
Example:
The greatest common divisor of 156, 84 and 90 is to be determined again.
First the GCD of 156 and 84 is determined with the Euclidean algorithm and then the GCD of the intermediate result and 90:
| 156 | : | 84 | = | 1 | R | 72 |
| 84 | : | 72 | = | 1 | R | 12 |
| 72 | : | 12 | = | 6 | R | 0 |
Result: gcd(156, 84) = 12
| 90 | : | 12 | = | 7 | R | 6 |
| 12 | : | 6 | = | 2 | R | 0 |
Result: gcd(12, 90) = 6
So it applies gcd(156, 84, 90) = gcd(gcd(156, 84), 90) = 6.
What can you do with the GCD?
The greatest common divisor can be used, among other things, to simplify fractions. To do this, simply calculate the GCD of the numerator and denominator and then divide both the numerator and denominator by the GCD.
| 156 |
| 84 |
| 13 |
| 7 |