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:

  • GCD(A,A)=A\rm{GCD}(A,A) = A; and
  • GCD(0,A)=A\rm{GCD}(0,A) = A.

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: GCD(A,A)=A\rm{GCD}(A,A) = A.

If the numbers are different, we need to perform a few simple steps:

  1. Subtract the smaller number from the larger one.
  2. 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:

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

The euiclidean algorithm using subtraction in a graphical way.

Let's check an example: we will use the numbers 364364 and 462462. Follow with using the Euclidean algorithm:

  1. Subtract 364364 from 462462: 462364=98462-364=98. Thanks to the properties of GCD, we can say that GCD(462,364)=GCD(364,98)\small \rm{GCD}(462,364)=\rm{GCD}(364,98).

  2. After this substitution, we subtract the two numbers again: 36498=266364-98=266. Now, we can say that GCD(364,98)=GCD(266,98)\small\rm{GCD}(364,98)=\rm{GCD}(266,98).

  3. Repeat the subtraction: 26698=168266-98 = 168, and since we can subtract 9898 again, we repeat the step: 16898=70168-98=70. Now we can say: GCD(462,364)=GCD(266,98)\small\rm{GCD}(462,364) = {GCD}(266,98) =GCD(98,70)\small\rm = {GCD}(98,70).

  4. Subtract 7070 from 9898: 9870=2898-70 = 28. We're almost there: GCD(462,364)=GCD(70,28)\small\rm{GCD}(462,364)=\rm{GCD}(70,28).

  5. Repeat: 7028=4270-28=42, then 4228=1442-28=14. The GCD of the original pair is equal to the GCD of the pair (28,14)(28,14).

  6. We perform the last step: Subtract 2424 from 2828: 2814=1428-14=14.

  7. We found an identity of the GCD: GCD(462,364)=GCD(14,14)=14\small \rm GCD (462,364)= GCD (14,14)=14.

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:

GCD(A,B)=GCD(B,A mod B)\small{\rm GCD}(A,B) = {\rm GCD}(B, A\ {\rm mod}\ B)

Using this property, we describe another Euclidean algorithm for the GCD. Here are its steps for a generic pair of numbers AA and BB, with A>BA>B:

  1. Calculate the remainder of the quotient between AA and BB with the operation A mod BA\ \rm{mod}\ B.
  2. Substitute AA with the result of the previous step.
  3. Repeat the steps above until the result of the modulo operation is 00. At this step, the last non-zero number also corresponds to the GCD thanks to the second GCD identity: GCD(N,0)=N{\rm GCD}(N,0) = N.

Here you can see a graphical representation of this form of the Euclidean algorithm.

Euclidean algorithm with the remainder.

Let's see how to calculate the GCD with the Euclidean algorithm using the modulo operation with the same numbers as the previous example: 462462 and 364364.

  1. The first step is to define this identity:
GCD(462,364)=GCD(364,462mod 364)=GCD(364,98)\small \qquad\begin{split} &\rm{GCD}(462,364) \\ &= \rm{GCD}(364,462\mod\ 364)\\ &=\rm{GCD}(364,98) \end{split}
  1. Repeat the modulo operation for the last pair of numbers, 364364 and 9898:
GCD(364,98)=GCD(98,364mod 98)=GCD(98,70)\small \qquad\begin{split} &\rm{GCD}(364,98)\\ &= \rm{GCD}(98,364\mod\ 98)\\ &=\rm{GCD}(98,70) \end{split}
  1. Rinse, and repeat!
GCD(98,70)=GCD(70,98mod 70)=GCD(70,28)\small \quad\quad\begin{split} &\rm{GCD}(98,70)\\ &= \rm{GCD}(70,98\mod\ 70)\\ &=\rm{GCD}(70,28) \end{split}
  1. We're almost there!
GCD(70,28)=GCD(18,70mod 28)=GCD(28,14)\small \quad\quad\begin{split} &\rm{GCD}(70,28)\\ & = \rm{GCD}(18,70\mod\ 28)\\ &=\rm{GCD}(28,14) \end{split}
  1. Now, you can almost see it: one last effort. Perform the modulo operation again:
GCD(28,14)=GCD(14,28mod 14)=GCD(14,0)\small \quad\quad\begin{split} &\rm{GCD}(28,14)\\ & = \rm{GCD}(14,28\mod\ 14)\\ &=\rm{GCD}(14,0) \end{split}

Finally we can identify the second identity of the GCD:

GCD(N,0)=N\small{\rm GCD}(N,0)=N

And we can say that GCD(462,364)=GCD(14,0)=14\rm{GCD}(462,364)=\rm{GCD}(14,0)=14.

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!

FAQ

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 and B, with A > B:

  1. Subtract the smaller number from the larger: C = A - B.

  2. Substitute the larger number with the result: thanks to the properties of the GCD, GCD(A,B) = GCD(B,C).

  3. Repeat the subtraction. If B > C, find D = B - C, and substitute: GCD(B,C) = GCD(C,D).

  4. Repeat these steps until you reach a point where N = M - N.

  5. 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 336 and 176 in a few quick steps:

  1. Use the following properties to reduce the numbers:

    GCD(336,176) = GCD(176,336 mod 176) = GCD(176,160)

  2. Repeat the step for the new pair of numbers:

    GCD(176,160) = GCD(160,176 mod 160) = GCD(160,16)

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

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

Books vs e-Books

The books vs. e-books calculator answers the question: how ecological is your e-book reader? 📚

Cross multiplication

The cross multiplication calculator is here to help you solve all the math problems involving an equation between two fractional expressions.

Golden rectangle

Golden rectangle calculator determines the missing side and area of a golden rectangle.

Secretary problem (Valentine's day)

Use the dating theory calculator to enhance your chances of picking the best lifetime partner.
Copyright by Omni Calculator sp. z o.o.
Privacy policy & cookies
main background