Euclidean Algorithm Calculator
With Omni's Euclidean algorithm calculator, you will learn an elegant and intriguing algorithm to find the greatest common divisor of any set of integer numbers. Keep reading this short article to learn:
- What is the Euclidean algorithm;
- What are the two types of Euclidean algorithms to calculate the GCD;
- Explanation step-by-step of the two algorithms;
- Expansion of the Euclidean algorithms to larger sets of numbers; and
- Some practical examples.
What is the Euclidean algorithm?
The Euclidean algorithm is an iterative process that allows you to calculate the greatest common divisor of a set of numbers without having to calculate the prime factorization, a process that can be long and highly demanding in resources.
The core concept of the Euclidean algorithm is to use the properties of the greatest common divisor to reduce the problem to a more manageable one.
We can identify two properties of the greatest common divisor that allow us to calculate the Euclidean algorithm for the GCD.
- The GCD of two numbers is also the GCD of their difference.
- The GCD of two numbers is also the GCD of the remainder of their quotient.
Using these two properties, we hope to reach a point where we can use two fundamental identities of the GCD:
- ; and
Calculate the Euclidean algorithm for the GCD: subtraction method
Let's see how we can translate the first property of the GCD into a working algorithm. We will start with two numbers.
We can weed out a special case from the beginning: if the two numbers are identical, then we already meet the first of the two identities: .
If the numbers are different, we need to perform a few simple steps:
- Subtract the smaller number from the larger one.
- Substitute the larger number with the result of the previous step.
Before going on with the algorithm, let's wait and understand this step. We substituted the pair of numbers with an updated pair, but it maintains the same GCD. The Euclidean algorithm to calculate the GCD with subtraction is a simple repetition of the following steps:
- Repeat steps 1. and 2. until the numbers in the pair are identical. The number appearing twice in the final pair is also the GCD of the original pair.
In the diagram below, you can see a graphical representation of the Euclidean algorithm for the greatest common divisor.
Let's check an example: we will use the numbers and . Follow with using the Euclidean algorithm:
Subtract from : . Thanks to the properties of GCD, we can say that .
After this substitution, we subtract the two numbers again: . Now, we can say that .
Repeat the subtraction: , and since we can subtract again, we repeat the step: . Now we can say: .
Subtract from : . We're almost there: .
Repeat: , then . The GCD of the original pair is equal to the GCD of the pair .
We perform the last step: Subtract from : .
We found an identity of the GCD: .
We admit it; it was pretty long. Can we find a way to speed things up?
Euclidean algorithm for the greatest common divisor using the modulo operation
Let's use the second property of the GCD: the GCD of two numbers is also the GCD of the remainder of their quotient. In mathematical terms, we say:
Using this property, we describe another Euclidean algorithm for the GCD. Here are its steps for a generic pair of numbers and , with :
- Calculate the remainder of the quotient between and with the operation .
- Substitute with the result of the previous step.
- Repeat the steps above until the result of the modulo operation is . At this step, the last non-zero number also corresponds to the GCD thanks to the second GCD identity: .
Here you can see a graphical representation of this form of the Euclidean algorithm.
Let's see how to calculate the GCD with the Euclidean algorithm using the modulo operation with the same numbers as the previous example: and .
- The first step is to define this identity:
- Repeat the modulo operation for the last pair of numbers, and :
- Rinse, and repeat!
- We're almost there!
- Now, you can almost see it: one last effort. Perform the modulo operation again:
Finally we can identify the second identity of the GCD:
And we can say that .
What is the Euclidean algorithm for more than two numbers?
Can we use the Euclidean algorithms to calculate the greatest common divisor of more than two numbers? The answer is yes! Simply create enough pairs to include all numbers at least once (this will be easy for even sets and slightly redundant for odd sets). If the result of the Euclidean algorithms applied to these sets is different, then rerun the algorithms on the results. Or use our Euclidean algorithm calculator for an easy and error-less answer!
Other GCD related tools
Try our other tools related to the calculations of the GCD:
What are the steps of the Euclidean algorithm for the GCD?
The steps of the Euclidean algorithm using subtraction are, for a pair of numbers
A > B:
Subtract the smaller number from the larger:
C = A - B.
Substitute the larger number with the result: thanks to the properties of the GCD,
GCD(A,B) = GCD(B,C).
Repeat the subtraction. If
B > C, find
D = B - C, and substitute:
GCD(B,C) = GCD(C,D).
Repeat these steps until you reach a point where
N = M - N.
Use this identity to find the GCD:
GCD(A,B) = GCD(N,N) = N
What is the GCD of 336 and 176 using the Euclidean algorithm?
Using the Euclidean algorithm with the remainder, we find the GCD of
176 in a few quick steps:
Use the following properties to reduce the numbers:
GCD(336,176) = GCD(176,336 mod 176) = GCD(176,160)
Repeat the step for the new pair of numbers:
GCD(176,160) = GCD(160,176 mod 160) = GCD(160,16)
In the last step, use the identity
GCD(N,0) = N:
GCD(160,16) = GCD(16,160 mod 16) = GCD(16,0) = 16
What is the best way to find the GCD of two numbers?
In most cases, using the Euclidean algorithm, either with subtraction (easier by hand) or the remainder (fastest but more complex), is a quick and safe way to calculate the GCD of two numbers. No guessing is involved (as in the prime factorization method), and it generally reaches a result in a reasonable number of operations.