Euclidean Algorithm

From Math Images

Revision as of 19:03, 14 July 2011 by PhoebeJiang (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

Euclid's Method to find the gcd

Fields: Number Theory and Algebra
Created By: Phoebe Jiang Website: [ ]

Euclid's Method to find the gcd

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

Here I use 52 and 36 as an example to show you how Euclid found the gcd, so you have a sense of the Euclidean algorithm in advance. As you have probably noticed already, Euclid uses lines, defined as multiples of a common unit length, to represent numbers. 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.

You may have many questions so far: "What is going on here?" "Are you sure that 4 is the gcd of 52 and 36?" Don't worry. We will talk about them precisely later. This brief explanation is just to preheat your enthusiasm for Euclidean Algorithm! It is amazing to see that he explains and proves his algorithm relying on visual graphs, which is different from how we treat number theory now.

1 Basic Description
2 A More Mathematical Explanation
- 2.1 The Description of Euclidean Algorithm
- 2.2 Proof of the Euclidean Algorithm
  - 2.2.1 Modern Proof
  - 2.2.2 Euclid's Proof
3 Extended Euclidean Algorithm
4 Efficiency
- 4.1 Number of Steps - Lamé's Theorem
- 4.2 Shortcomings of the Euclidean Algorithm
5 Why It's Interesting
6 Teaching Materials
7 References
8 Future Directions for this Page

Basic Description

We all know that 1 divides every number and that no positive integer is smaller than 1, so 1 is the smallest common divisor for any two integers a and b. Then what about the greatest common divisor? Finding the gcd is not as easy as finding the smallest common divisor.

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

About 2000 years ago, Euclid, one of the greatest mathematician of Greece, devised a fairly simple and efficient algorithm to determine the gcd 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.

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.

The Euclidean algorithm comes in handy with computers because large numbers are hard to factor but relatively easy to divide. It is used in many other places and we’ll talk about its applications later.

A More Mathematical Explanation

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

The Description of Euclidean Algorithm

Mathematical definitions and their abbreviations

' [...]

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.

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 $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 of $r = a - kb$ , $r = q_1 d - k q_2 d = (q_1 - k q_2) d$ and we will get $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

Divide a by b and get the remainder r.
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.

168 = 2 $\times$ 64 + 40

64 = 1 $\times$ 40 + 24

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

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. Then we will show that it is the greatest. Recall that

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

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

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

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

... ...

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

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

Based on the last two equations, we substitute $r_{n -1}$ with $k_nr_n$ in the last to second equation such that $r_{n -2} = k_{n -1}r_{n -1} + r_n = k_{n -1}k_nr_n + r_n = (k_{n -1}k_n + 1) r_n$ .

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

From the equation before those two, 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.

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:

Because $a = k_0b + r_1$ Therefore $r_1 = a - k_0b = dm - k_0 dn = (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. Solve for $r_2$ in the same way. Because $b = k_1r_1 + r_2$ Therefore $r_2 = b - k_1r_1= dn - k_1d_1 d = (n - k_1d_1) d$ Thus, $d \mid r_2$

Continuing the process until we reach the last equation, 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.^[1]

NOTES:

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.

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. ^[1] [VII.Def.12] Q.E.D.

NOTE :

Here is a translation of Proposition 1.

Write Euclid's proof in several equations and assume a > b. We will get:

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

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

$r = lt + <font color=red>1</font>, \quad 1 < r$

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

Assume a and b have a common measure e (e >1); then e measures or divides r based on the first equation above and e divides t based on the second equation above. Hence, e measures r and 1, but e cannot measure (divide) 1. Therefore, a and b are prime to each other.

Proposition 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. ^[1] Q.E.D

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 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 biggest common divisor.

Extended Euclidean Algorithm

Expand the Euclidean algorithm and you will be able to solve Bézout's identity for x and y when 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 a,b are bigger than gcd(a, b) more often than not.

Recall that

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

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

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

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

... ...

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

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

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

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

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

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

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

Substitute Eq. 2 into Eq. 1:

$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}$
$gcd(a, b)$	$=$	$(1 + k_{n-1}k_{n-2})r_{n-2} - k_{n-1}r_{n-3}$

Now you can see gcd(a, b) is expressed by a linear combination of $r_{n-2}$ and $r_{n-3}$ based on the last two equations. 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.

The description of the extended Euclidean algorithm:

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

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

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

Use the extended Euclidean algorithm to get x and y:

From the fourth equation we get

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

From the third equation we get

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

Substitute Eq. 4 into Eq. 3:

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: 24 = 64 - 1 $\times$ 40

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

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

From the first equation we get 40 = 168 - 2 $\times$ 64

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

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

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

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

Efficiency

Number of Steps - Lamé's Theorem

Gabriel Lamé is the first person who shows the number of steps required by the Euclidean algorithm. His 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$

The number of steps is n+1.

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

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

From the last equation $r_{n -1} = k_nr_n$ , we know that $r_{n- 1} > r_n$ . Thus, $k_n$ should be bigger than 1: $k_n \geqslant 2$ . Therefore, $r_{n -1} = k_nr_n \geqslant 2 r_n \geqslant 2F_2 = F_3$ .

For the integer $k_{n -1}$ , we must have $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$ .

So far, we have 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 \geqslant \log_{10} \alpha ^n = n \log_{10} \alpha \approx n 0.208 \approx \frac{n}{5}$

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

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

$5k > n$

$5k +1 > n + 1$

$5k \geqslant n + 1$

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

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 with addition, subtraction and shifts, which make it easier for the CPU to compute large integers.

The 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 gcd( $\frac{e}{2}, \frac{f}{2}$ ), because 2 is definitely a common divisor of two even integers.
If e is even and v is odd, then gcd(e, f) = gcd( $\frac{e}{2}$ , f), 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( $\frac{|e-f|}{2}$ , the smaller one of e and f). According to Euclidean algorithm, the difference of e and f could also divide the gcd of e and f. And Euclidean algorithm with a division by 2 results in an integer because the difference of two odd integers is even.

The description of Stein's algorithm:

Input: $u, v ( 0 < u \leqslant v )$ ;

Output: g = gcd(u, v)

Inner Computation:

g = 1.
While both u and v are even integers, do $u = \frac{u}{2}, v = \frac{v}{2}, g = 2g$ .
While , 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.
Return ( $g \cdot v$ )

Example: $u=168, v=64$

$u = \frac{168}{2} = 84, v = \frac{64}{2} = 32, g = 2$ ; $u = \frac{84}{2} = 42, v = \frac{32}{2} = 16, g = 4$ ; $u = \frac{42}{2} = 21, v = \frac{16}{2} = 8, g =8$ ;
1. $v = \frac{8}{2} = 4; v = \frac{4}{2} = 2; v = \frac{2}{2} = 1;$
2. $t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10$ ,
3. $\because u = 21 > 1 = v, \therefore u = t =10;$
1. $u = \frac{10}{2} = 5;$
2. $t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2,$
3. $\because u = 5 > 1 = v, \therefore u = t = 2;$
1. $u = \frac{2}{2} = 1;$
2. $t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0,$
3. $\because u = 2 > 1 = v, \therefore u = t = 0;$
$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 The Application of 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

More applets or animations of Euclidean algorithm.
More pictures if possible.
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.

Retrieved from "http://mathforum.org/mathimages/index.php/Euclidean_Algorithm"

Categories: Higher Education | Math Images In Progress | Number Theory | Algebra | Phoebe Jiang

Euclidean Algorithm

From Math Images

Contents

Basic Description

A More Mathematical Explanation

The Description of Euclidean Algorithm

Mathematical definitions and their abbreviations

The Description of Euclidean Algorithm

Mathematical definitions and their abbreviations

Precondition

Description

Example

Proof of the Euclidean Algorithm

Modern Proof

Euclid's Proof

Extended Euclidean Algorithm

Efficiency

Number of Steps - Lamé's Theorem

Shortcomings of the Euclidean Algorithm

Why It's Interesting

Teaching Materials

References

Future Directions for this Page

Views

Personal tools

Navigation

Search

Browse images by...

Interaction

Create or Edit a Page

Special Resources

Toolbox