Euclidean Algorithm

Euclidean Algorithm
Fields: Number Theory and Algebra
Image Created By: Phoebe Jiang

Euclidean Algorithm

About 2000 years ago, Euclid, one of the greatest mathematician of Greece, devised a fairly simple and efficient algorithm to determine the greatest common divisor of two integers, which is now considered as one of the most efficient and well-known early algorithms in the world. The Euclidean algorithm hasn't changed in 2000 years and has always been the the basis of Euclid's number theory.

This image shows Euclid's method to find the greatest common divisor of two integers. The greatest common divisor of two numbers a and b is the largest integer that divides the numbers without a remainder.

Basic Description

When asked to find the gcd of two integers, a possible way is to prime factor each integer and see which factors are common between the two, or we could simply try different numbers and see which number works. However, both approaches could be very complicated and time consuming as the two integers become relatively large.

Euclidean algorithm (also known as Euclid’s algorithm) describes a procedure for finding the greatest common divisor of two positive integers. This method is recorded in Euclid’s Elements Book VII. This book contains the foundation of number theory for which Euclid is famous.

An example of the method is shown in the image. First, use the smaller integer of the two, 36, to divide the bigger one, 52. Use the remainder of this division, 16, to divide 36 and you get the remainder 4. Now divide the last divisor, 16, by 4 and you find that they divide exactly. Therefore, 4 is the greatest common divisor. For every two integers, you will get the gcd by repeating the same process until there is no remainder

The Euclidean algorithm comes in handy with computers because large numbers are hard to factor but relatively easy to divide.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Number Theory, Algebra

[Click to view A More Mathematical Explanation]

The Description of Euclidean Algorithm

Mathematical definitions and their abbreviations

• ' [...]

[Click to hide A More Mathematical Explanation]

The Description of Euclidean Algorithm

Mathematical definitions and their abbreviations

• a mod b is the remainder when a is divided by b (where mod = modulo).

Example: 7 mod 4 = 3; 4 mod 2 = 0; 5 mod 9 = 5

• a $\mid$ b means a divides b exactly or b is divided by a without any remainder.

Example: 3 $\mid$ 6 ; 4 $\mid$ 16

• gcd means the greatest common divisor, also called the greatest common factor (gcf), the highest common factor (hcf), and the greatest common measure (gcm).
• gcd(a, b) means the gcd of two positive integers a and b; (a, b) is another notation for gcd(a, b).

Keep those abbreviations in mind; you will see them a lot later.

Precondition

The Euclidean Algorithm is based on the following theorem:

Theorem: $gcd(a, b) = gcd(b,~ a~mod~b)$ where $a > b$ and $a~ mod~ b ~\ne 0$.

Proof:

Since $a > b$, $a$ could be denoted as $a = kb + r$ with $0 \leqslant r < b$.

Then the remainder $r = a~mod~b$.

Assume $d$ is a common divisor of $a$ and $b$, thus $d \mid a , d\mid b$, or we could write them as $a= q_1 d, b = q_2 d.$

Because $r = a - kb$,

$r = q_1 d - k q_2 d = (q_1 - k q_2) d$, so we know $d \mid r$.

Therefore $d$ is also a common divisor of $(b, r) = (b, a~mod~b)$.

Hence, the common divisors of $(a, b)$ and $(b, a~mod~b)$ are the same.

In other words, $(a, b)$ and $(b, a~mod~b)$ have the same common divisors, and so they have the same greatest common divisor.

Description

The description of the Euclidean algorithm is as follows:

• Input two positive integers, a,b (a > b)

• Output g, the gcd of a, b

• Internal Computation

1. Divide a by b and get the remainder r.
2. If r=0, report b as the gcd of a and b. If r $\ne$0, replace a by b and replace b by r. Go back to the previous step.

---

The algorithm process is like this:

$a = k_0b + r_1, \quad 0 < r_1 < b$

$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$

$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$

$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$

... ...

$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad 0 < r_{n -1} < r_n$

$r_{n -1} = k_nr_n, \quad\quad\quad\quad r_n = 0$

To sum up,

$(a, b) = (b, r_1) = (r_1, r_2) = (r_2, r_3) = (r_3, r_4) = ... ... =(r_{n- 2}, r_{n -1}) = (r_{n- 1}, r_n)$

$r_n$ is the gcd of a and b.

Note: The Euclidean algorithm is iterative, meaning that the next step is repeated using the result from the last step until it reaches the end.

Example

An example will make the Euclidean algorithm clearer. Let's say we want to know the gcd of 168 and 64.

In this case, a = 168, b = 64. Start writing the first equation:

168 = 2 $\times$ 64 + 40

(Try to find the greatest possible coefficient (integer) for quotient 64. Couldn't be 1 because the remainder has to be smaller than then quotient 64. Couldn't be 3 otherwise it is greater than 168. So it turns out to be 2 and the remainder is 40.)

64 = 1 $\times$ 40 + 24

(Get the remainder 40 from the last equation. $r_1 = 40$. Use it as the quotient for this second equation. By analog, find the coefficient for 40 and the remainder.)

40 = 1 $\times$ 24 + 16

24 = 1 $\times$ 16 + 8

16 = 2 $\times$ 8

(168, 64) = (64, 24) = (24, 16) = (16, 8)

Therefore, 8 is the gcd of 168 and 64.

• Here's an applet for you to play around with finding the gcd by using the Euclidean algorithm.

Proof of the Euclidean Algorithm

Modern Proof

• Proving That It Is A Common Divisor

In order to prove that Euclidean algorithm works, the first thing is to show that the number we get from this algorithm is a common divisor of a and b. Recall that

Eq. 1         $a = k_0b + r_1, \quad \quad \quad \quad \quad0 < r_1 < b$

Eq. 2         $b = k_1r_1 + r_2 , \quad \quad \quad \quad \quad 0 < r_2 < r_1$

Eq. 3         $r_1 = k_2r_2 + r_3, \quad \quad \quad \quad \quad 0 < r_3 < r_2$

... ...

Eq. n-1        $r_{n-3} = k_{n-2}r_{n-2} + r_{n -1}, \quad \quad 0 < r_{n-2} < r_{n -1}$

Eq. n         $r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad \quad 0 < r_{n -1} < r_n$

Eq. n+1        $r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad \quad r_n = 0$

Based on the last equation Eq. n+1, we substitute $r_{n -1}$ with $k_nr_n$ in Eq. n such that

$r_{n -2} = k_{n -1}r_{n -1} + r_n = k_{n -1}k_nr_n + r_n$.

$r_{n-2} = (k_{n -1}k_n + 1) r_n$

Thus we have $r_n \mid r_{n -2}$.

From the equation before those two Eq. n-1, we repeat the steps we did just now: $r_{n -3} = k_{n -2}r_{n -2} + r_{n -1} = k_{n -2} \Big( (k_{n -1} k_n + 1)r_n \Big) + k_nr_n = (k_{n -2} k_{n -1} k_n + k_{n - 2} + k_n) r_n$.

Now we know $r_n \mid r_{n -3}$.

Continue this process and we will find that $r_n \mid a, r_n \mid b$, so $r_n$, the number we get from Euclidean algorithm, is indeed a common divisor of a and b.

• Proving That It Is The Greatest

Second, we need to show that $r_n$ is the greatest among all the common divisors of a and b. To show that $r_n$ is the greatest, let's assume that there is another common divisor of a and b, d, where d is a positive integer. Then we could rewrite a and b as a = dm , b = dn, where m and n are also positive integers. This second part of the proof is going to be similar to the first part because they both repeat the same steps and eventually get the result, but this time we start from the first equation of the Euclidean algorithm Eq. 1:

We know that $a = k_0b + r_1$. Thus,

$r_1 = a - k_0b = dm - k_0 dn$, and

$r_1 = (m - k_0 n) d$ (substitute dm for a and dn for b).

Therefore, $d \mid r_1$. Let $r_1 = d_1 d$.

Consider the second equation Eq. 2. Solve for $r_2$ in the same way.

We know that $b = k_1r_1 + r_2$. Thus,

$r_2 = b - k_1r_1= dn - k_1d_1 d$, and

$r_2 = (n - k_1d_1) d$.

Therefore, $d \mid r_2$.

Continuing the process until we reach the last equation Eq. n, we will get $d \mid r_n$. Since we pick d to represent any possible common divisor of a and b except $r_n, d \mid r_n$ means that $r_n$ divides any other common divisor of a and b, meaning that $r_n$ must be greater than all the other common divisors. Therefore, the number we get from the Euclidean Algorithm, $r_n$, is indeed the greatest common divisor of a and b.

Euclid's Proof

Now let's look at Euclid's proof. Since Euclid's method of finding the gcd is based on several definitions, I quote the first 15 definitions in Book VII of his Elements for you.

Definitions

1. A unit is that by virtue of which each of the things that exist is called one.

2. A number is a multitude composed of units.

3. A number is a part of a number, the less of the greater, when it measures the greater.

4. but parts when it does not measure it.

5. The greater number is a multiple of the less when it is measured by the less.

6. An even number is that which is divisible into two equal parts.

7. An odd number is that which is not divisible into two equal parts, or that which differs by an unit from an even number.

8. An even-times even number is that which is measured by an even number according to an even number.

9. An even-times odd number is that which is measured by an even number according to an odd number.

10. An odd-times odd number is that which is measured by an odd number according to an odd number.

11. A prime number is that which is measured by an unit alone.

12. Numbers prime to one another are those which are measured by an unit alone as a common measure.

13. A composite number is that which is measured by some number.

14. Numbers composite to one another are those which are measured by some number as a common measure.

15. A number is said to multiply a number when that which is multiplied is added to itself as many times as there are units in the other, and thus some number is produced.

Editor's Note:

In a nutshell, Euclid's one unit is the number 1 in algebra. He uses lines to represent numbers; the longer the line the greater the number.

In Def.3, "measure" means "divide."

Proposition 1. (See Image 1)

Two unequal numbers being set out, and the less being continually subtracted in turn from the greater, if the number which is left never measures the one before it until an unit is left, the original numbers will be prime to one another.

For, the less of two unequal numbers AB, CD being continually subtracted from the greater, let the number which is left never measure the one before it until an unit is left;

image 1

I say that AB, CD are prime to one another, that is, that an unit alone measures AB, CD.

For, if AB, CD are not prime to one another, some number will measure them.

Let a number measure them, and let it be E; let CD, measuring BF, leave FA less then itself,

let, AF measuring DG, leave GC less than itself, and let GC, measuring FH, leave an unit HA.

Since, then, E measures CD, and CD measure BF, therefore E also measures BF.

But it also measures the whole BA;

therefore it will also measure the remainder AF.

But AF measures DG;

therefore E also measures DG.

But it also measures the whole DC;

therefore it will also measure the remainder CG.

But CG measures FH;

therefore E also measures FH.

But it also measures the whole FA;

therefore it will also measure the remainder, the unit AH, though it is a number: which is impossible.

Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. [VII.Def.12] Q.E.D.

Editor's Note :

Here is my translation of Proposition 1.

Euclid wants to show that a and b must be prime to each other if we get 1 left instead of 0. Why?

Recall a > b. Write Euclid's proof in equations and we will get:

$a = kb + r, \quad 0 < r < b$

$b = qr + t, \quad 0 < t < r$

$r = lt + {\color{Red}1}, \quad 1 < r$

Assume a and b have a common measure e with e greater than one. Then e measures or divides r based on the first equation above, and e divides t based on the second equation above. Hence, e divides r and 1, but e cannot divide 1. In other words, 1 cannot be divided by e without any remainder because e is greater than 1. Therefore, a and b are prime to each other.

Proposition 2. (See Image 2)

Given two numbers not prime to one another, to find their greatest common measure.

Let AB, CD be the two given numbers not prime to one another.

Thus it is required to find the greatest common measure of AB, CD.

If now CD measures AB - and it also measures itself - CD is a common measure of CD, AB.

And it is manifest that it is also the greatest; for no greater number than CD will measure CD.

But, if CD does not measure AB, then, the less of the numbers AB, CD being continually subtracted from the greater, some number will be left which will measure the one before it.

For an unit will not be left; otherwise AB, CD will be prime to one another [VII, I], which is contrary to the hypothesis.

image 2

Therefore, some number will be left which will measure the one before it.

Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.

Since then, CF measures AE, and AE measures DF,

therefore CF will also measure DF.

But it also measures itself;

therefore it will also measure the whole CD.

But CD measures BE;

therefore CF also measures BE.

But it also measures EA;

therefore it will also measure the whole BA.

But it also measures CD;

therefore CF measures AB, CD.

Therefore CF is a common measure of AB, CD.

I sat next that it is also the greatest.

For, if CF is not the greatest common measure of AB, CD, some number which is greater than CF will measure the numbers AB, CD.

Let such a number measure them, and let it be G.

Now, since G measures CD, while CD measures BE, G also measures BE.

But it also measures the whole BA;

therefore it will also measure the remainder AE.

But AE measures DF;

therefore G will also measure DF.

But it also measures the whole DC;

therefore it will also measure the remainder CF, that is, the greater will measure the less: which is impossible.

Therefore no number which is greater than CF will measure the number AB, CD;

therefore CF is the greatest common measure of AB, CD.

PORISM. From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. Q.E.D

‘’Editor's Note:

Prop.2 is pretty self-explanatory, proved in a similar way as Prop.1.

Comparing the modern proof with Euclid's proof, it is not hard to notice that the modern proof is more about algebra, while Euclid did his proof of his algorithm using geometry because, at that time, algebra had not been invented yet. However, the main idea is pretty much the same. They both prove that the result is a common divisor first and then show that it is the greatest among all the common divisors.

Extended Euclidean Algorithm

Expand the Euclidean algorithm and you will be able to solve Bézout's identity for x and y where d = gcd(a, b):

$ax +by = gcd(a, b).$

Note: Usually either x or y will be negative since a, b and gcd(a, b) are positive and both a and b are usually greater than gcd(a, b).

Description

The description of the extended Euclidean algorithm is:

Input: Two non-negative integers a and b ( $a \leqslant b$).

Output: d = gcd(a, b) and integers x and y satifying ax + by = d.

Computation:

• If $b = 0,$ set $d = a, x = 1, y = 0,$ and return $(d, x, y).$
• If not, set$x_2 = 1, x_1 = 0, y_2 = 0, y_1 = 1$
• While $b > 0$, do

$q = floor(\frac{a}{b}), r = a - qb, x = x_2 - qx_1, y = y_2 - q y_1.$

$a = b, b = r, x_2 = x_1, x_1 = x, y_2 = y_1, y_1 = y.$

• Set $d = a, x = x_2, y = y_2,$ and return $(d, x, y).$

Example

This linear equation is going to be very complicated with all these notations, so it is much easier to understand with an example:

Solve for integers x and y such that 168x + 64y = 8.

• Apply Euclidean algorithm to compute gcd(168, 64), and we have a list of the following equations:

$168 = 2 \times 64 + 40$

$64 = 1 \times 40 + 24$

$40 = 1 \times 24 + 16$

$24 = 1 \times 16 + 8$

$16 = 2 \times 8 + 0$

Thus gcd(168, 64) = 8. So we know that we can solve for x and y by extended Euclidean algorithm.

• Use the extended Euclidean algorithm to get x and y:

From the fourth equation we get

Eq. 6         $8 = 24 - 1 \times 16.$

From the third equation we get

Eq. 7         $16 = 40 - 1 \times 24$.

• Substitute Eq. 7 into Eq. 6:

$8 = 24 - 1 \times (40 - 1 \times 24)$

$8 = 24 - 1 \times 40 + 1 \times 24$

$8 = 2 \times 24 - 1 \times 40$

• Do the same steps for the second equation in the list: $24 = 64 - 1 \times 40$

$8 = 2\times (64 - 1 \times 40) - 1\times 40$

$8 = 2\times 64 - 3\times 40$

For the first equation in the list, we get $40 = 168 - 2 \times 64$

$8 = 2\times 64 - 3 \times (168 - 2 \times 64)$

$8 = -3 \times 168 + 8 \times 64$

$\therefore x = -3, y = 8$

Proof

Recall that

$a = k_0b + r_1, \quad 0 < r_1 < b$

$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$

$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$

$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$

... ...

$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad 0 < r_{n -1} < r_n$

$r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad r_n = 0$

Solve for $r_n$ using the second to last equation and we get:

$r_n = r_{n-2} - k_{n-1}r_{n-1}$

Because $r_n = gcd(a, b)$ by Euclidean algorithm,

Eq. 4        $gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1}$

Now let's solve for $r_{n-1}$ in the same way:

Eq. 5        $r_{n -1} = r_{n -3} - k_{n-2}r_{n-2}$

Substitute Eq. 5 into Eq. 4:

$gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1}$

$gcd(a, b) = r_{n -2} - k_{n -1}(r_{n -3} - k_{n-2}r_{n-2})$

$gcd(a, b) = r_{n -2} - k_{n -1}r_{n -3} + k_{n-1}k_{n-2}r_{n-2}$

${\color{Blue}gcd(a, b)} = (1 + k_{n-1}k_{n-2}){\color{Blue}r_{n-2}} - k_{n-1} {\color{Blue}r_{n - 3}}$

Now you can see gcd(a, b) is expressed by a linear combination of $r_{n-2}$ and $r_{n-3}$. If we continue this process by using the previous equations from the list above, we could get a linear combination of $r_{n-3}$ and $r_{n-4}$ with $r_{n-3}$ representing $r_{n-2}$ and $r_{n-4}$ representing $r_{n-3}$. If we keep going like this till we hit the first equation, we can express gcd(a, b) as a linear combination of a and b, which is what we intend to do.

Euclidean algorithm and extended Euclidean algorithm makes it elegantly easy to compute the two Bézout's coefficients.

Efficiency

How efficient could Euclidean algorithm be? Is it always perfect? Does Euclidean algorithm have shortcomings?

Number of Steps - Lamé's Theorem

Gabriel Lamé is the first person who shows the number of steps required by the Euclidean algorithm. Lamé's theorem states that the number of steps in Euclidean algorithm for gcd(a,b) is at most five times the number of digits of the smaller number b. Thus, the Euclidean algorithm is linear-time in the number of digits in b.

Proof

Recall the division equations from the Euclidean algorithm,

$a = k_0b + r_1, \quad 0 < r_1 < b$

$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$

$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$

$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$

... ...

$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad 0 < r_n < r_{n -1}$

$r_{n -1} = k_nr_n, \quad r_{n+1} = 0$

We can tell from the equations that the number of steps is $n+1$ with n being the same n as in the division equations. So we want to prove that $n + 1 \leqslant 5k$ where k is the number of digits of b.

Notations:

1. a and b are integers and we assume a is bigger than b, so $a > b \geqslant 1$.
2. The Fibonacci Numbers are 1, 1, 2, 3, 5, 8, 13, ... , where every later number is the sum of the two previous numbers.
3. Denote $Fn$ as the nth Fibonacci number (i.e. $F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 8$).
4. All the numbers in the division equations, $a, b, r_n, k_n$, are positive integers.

Analyze the division equations and we will have three conclusions:

• $r_n$ couldn't be 0, as otherwise all the remainders would be 0. Hence, $r_n \geqslant 1 = F_2$.

• We know that $r_{n- 1} > r_n$. Thus, according to the last equation $r_{n -1} = k_nr_n$, $k_n$ should be greater than 1: $k_n \geqslant 2$. Therefore, $r_{n -1} = k_nr_n \geqslant 2 r_n \geqslant 2F_2 = 2 = F_3$.

• $k_{n -1}$ is an integer, so $k_{n -1} \geqslant 1$. Thus, $r_{n -2} \geqslant r_n + r_{n -1}$. Since $r_{n -1} \geqslant F_3$ and $r_{n} \geqslant F_2,$ we have $r_{n-2} \geqslant F_2 + F_3 = F_4$.

Simplify the three conclusions:

$r_n \geqslant 1 = F_2$

$r_{n -1} = k_nr_n \geqslant 2 r_n \geqslant 2F_2 = F_3$

$r_{n-2} \geqslant r_{n} + r_{n -1} \geqslant F_2 + F_3 = F_4$

According to induction,

$r_{n -3} \geqslant r_{n -1} + r_{n -2} \geqslant F_3 + F_4 = F_5$

...

$r_1 \geqslant r_3 + r_2 \geqslant F_{n- 1} + F_n = F_{n+1}$

$b \geqslant r_2 + r_1 \geqslant F_n + F_{n+1} = F_{n+2}$

Therefore, $b \geqslant F_{n + 2}$

A theorem about the lower bound of Fibonacci numbers states that for all integers $n \geqslant 3$, it is true that $F_n > \alpha ^{n -2}$ where $\alpha = \frac{1+\sqrt{5}}{2} \approx 1.61803$ ( the sum of the Golden Ratio and 1).

Therefore, $b \geqslant F_{n+2} > \alpha ^n$

Thus, $\log_{10} b > \log_{10} \alpha ^n = n \log_{10} \alpha \approx n~0.208 \approx \frac{n}{5}$

Because b has k digits, $k > \log_{10} b$. Then

$k > \log_{10} b > \frac{n}{5}$

$k > \frac{n}{5}$

$5k > n$

$5k +1 > n + 1$

$5k \geqslant n + 1$

$n + 1 \leqslant 5k$.

Therefore, the number of steps ($n + 1$) required by Euclidean algorithm for gcd(a,b) is no more than five times the number of digits of b ($5k$).

Shortcomings of the Euclidean Algorithm

The Euclidean algorithm is an ancient but good and simple algorithm to find the gcd of two nonnegative integers; it is well designed both theoretically and practically. Due to its simplicity, it is widely applied in many industries today. However, when dealing with really big integers (prime numbers over 64 digits in particular), finding the right quotients using the Euclidean algorithm adds to the time of computation for modern computers.

Stein's algorithm (also known as the binary GCD algorithm) is also an algorithm to compute the gcd of two nonnegative integers brought forward by J. Stein in 1967. This alternative is made to enhance the efficiency of the Euclidean algorithm, because it replaces complicated division and multiplication in Euclidean algorithm with addition, subtraction and shifts, which make it easier for the CPU to compute large integers.

Stein's algorithm has the following conclusions:

• $gcd(m, 0) = m, gcd(0, m) = m.$It is because every number except 0 divides 0 and m is the biggest number that can divide itself.
• If e and f are both even integers, then $gcd(e, f) = 2 \cdot gcd\left ( \frac{e}{2}, \frac{f}{2} \right )$, because 2 is definitely a common divisor of two even integers.

• If e is even and f is odd, then $gcd(e, f) = gcd \left ( \frac{e}{2}, f \right )$, because 2 is definitely not a common divisor of an even integer and an odd integer.

• Otherwise both are odd and $gcd(e, f) = gcd\left ( \frac{|e-f|}{2}, \mbox{the smaller one of e and f} \right )$. According to Euclidean algorithm, the difference of e and f, which is $|e-f|$, could also divide $gcd(e, f)$. And $\frac{|e-f|}{2}$ is an integer because the difference of two odd integers is even. Thus, the gcd of $\frac{|e-f|}{2}$ and the smaller one of e is the gcd of e and f.

Based on the three conclusions, Stein's algorithm is described as the following. Note that the inner computation below is actually the same as the three conclusions. We just restate the three conclusions in an "algorithm form."

Input: any two distinctive positive integers$u, v$ with $0 < u \leqslant v$;

Output: $g = gcd(u, v)$

Inner Computation:

1. g = 1.
2. While both u and v are even integers, do $u = \frac{u}{2}, v = \frac{v}{2}, g = 2g$; ( "while" means both "if" and "iteration until the condition is no longer satisfied" )
3. While $u > 0$, do:
   1. While u is even, do: $u =\frac{u}{2}$;
   2. While v is even, do: $v = \frac{v}{2}$;
   3. $t = \frac{\left\vert u - v \right\vert }{2}$;
   4. If $u \leqslant v , u = t$; else, $v = t;$
4. Return $g \cdot v$.

Example:

Steiner's algorithm is designed for large numbers, but we only provide an example with small numbers for convenience.

$u=168, v=64$

1. $g = 1$;
2. Both u and v are even integers.
   1. $u = \frac{168}{2} = 84, v = \frac{64}{2} = 32, g = 2$;
   2. $u = \frac{84}{2} = 42, v = \frac{32}{2} = 16, g = 4$;
   3. $u = \frac{42}{2} = 21, v = \frac{16}{2} = 8, g =8$; (u and v are not both even now. Move on to the next step.)
3. $u = 21 > 0;$
   1. v is even.
      1. $v = \frac{8}{2} = 4;$
      2. $v = \frac{4}{2} = 2;$
      3. $v = \frac{2}{2} = 1;$
   2. $t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10$,
   3. $u = 21 > 1 = v, \therefore u = t =10;$
4. $u = 10 > 0, v =1;$
   1. u is even.
      1. $u = \frac{10}{2} = 5;$
   2. $t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2,$
   3. $u = 5 > 1 = v, \therefore u = t = 2;$
5. $u = 2 > 0, v =1;$
   1. u is even.
      1. $u = \frac{2}{2} = 1;$
   2. $t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0,$
   3. $u = 2 > 1 = v, \therefore u = t = 0;$ ( Because u = 0, condition u > 0 is no longer satisfied. Move on to the next step)
6. Return $g = g \cdot v = 8 \times 1 = 8.$

Now you may have a better understanding of the efficiency of Stein's algorithm, which substitutes divisions with faster operations by exploiting the binary representation that real computers use nowadays.

Why It's Interesting

The Euclidean algorithm is a fundamental algorithm for other mathematical theories and various subjects in different areas. Please see Application of the Euclidean Algorithm to learn more about the Euclidean algorithm.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

References

[1] Loy, Jim. Euclid's Algorithm. Retrieved from http://www.jimloy.com/number/euclids.htm.

[2] Wikipedia(Extended Euclidean Algorithm). (n.d.). Extended Euclidean Algorithm. Retrieved from http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.

[3] Artmann, Benno. (1999) ‘‘ Euclid-the creation of mathematics.’’ New York: Springer-Verlag.

[4] Weisstein, Eric W. Euclidean Algorithm. From MathWorld--A Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/EuclideanAlgorithm.html.

[5] Bogomolny, Alexander. Euclid's Algorithm. Retrieved from http://www.cut-the-knot.org/blue/Euclid.shtml.

[6] Health, T.L. (1926) Euclid The Thirteen Books of the Elements. Volume 2, Second Edition. London: Cambridge University Press.

[7] Klappenecker, Andreas. Euclid's Algorithm. Retrieved from http://faculty.cs.tamu.edu/klappi/alg/euclid.pdf.

[8] Ranjan, Desh. Euclid’s Algorithm for the Greatest Common Divisor. Retrieved from http://www.cs.nmsu.edu/historical-projects/Projects/EuclidGCD.pdf.

[9] The Euclidean Algorithm. Retrieved from http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html.

[10] Caldwell, Chris K. Euclidean algorithm. Retrieved from http://primes.utm.edu/glossary/xpage/EuclideanAlgorithm.html.

[11] Gallian, Joseph A. (2010) Contemporary Abstract Algebra Seventh Edition. Belmont: Brooks/Cole, Cengage Learning.

[12] Milson, Robert. Euclid's Algorithm. Retrieved from http://planetmath.org/encyclopedia/EuclidsAlgorithm.html.

[13] Black, Paul E. Binary GCD Algorithm. Retrieved from http://ce.sharif.edu/~ghodsi/ds-alg-dic/HTML/binaryGCD.html.

[14] Wikipedia (Binary GCD Algorithm). (n.d.). Binary GCD Algorithm. Retrieved from http://en.wikipedia.org/wiki/Binary_GCD_algorithm.

[15] Caldwell, Chris K. Lame's Theorem. Retrieved from http://primes.utm.edu/glossary/xpage/LamesTheorem.html.

[16] University of Minnesota. Induction and Recursion. Retrieved from http://www-users.cselabs.umn.edu/classes/Fall-2009/csci2011/lecture35.pdf.

Future Directions for this Page

1. More applets or animations of Euclidean algorithm.
2. More pictures if possible.
3. Worst case of Euclidean algorithm.
   

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.