Euclidean Algorithm
From Math Images
Line 33:  Line 33:  
:''Example:'' 3 <math>\mid</math> 6 ; 4 <math>\mid</math> 16  :''Example:'' 3 <math>\mid</math> 6 ; 4 <math>\mid</math> 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''' 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.  +  * '''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.  Keep those abbreviations in mind; you will see them a lot later.  
Revision as of 13:08, 15 July 2011
Euclid's Method to find the gcd 

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.
Contents 
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 wellknown 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
 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 b means a divides b exactly or b is divided by a without any remainder.
 Example: 3 6 ; 4 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: where and
 Proof: Since , could be denoted as with . Then . Assume is a common divisor of and , thus , or we could write them as Because of , and we will get. Therefore is also a common divisor of . Hence, the common divisors of and are the same. In other words, and 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 0, replace a by b and replace b by r. Go back to the previous step.
The algorithm process is like this:
 ... ...
To sum up,
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 64 + 40
64 = 1 40 + 24
40 = 1 24 + 16
24 = 1 16 + 8
16 = 2 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
 ... ...
Based on the last two equations, we substitute with in the last to second equation such that .
Thus we have .
From the equation before those two, we repeat the steps we did just now: .
Now we know .
Continue this process and we will find that , so , the number we get from Euclidean algorithm, is indeed a common divisor of a and b.
Second, we need to show that is the greatest among all the common divisors of a and b. To show that 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 Therefore (substitute dm for a and dn for b)
Therefore, . Let .
Consider the second equation. Solve for in the same way. Because Therefore Thus,
Continuing the process until we reach the last equation, we will get . Since we pick d to represent any possible common divisor of a and b except means that divides any other common divisor of a and b, meaning that must be greater than all the other common divisors. Therefore, the number we get from the Euclidean Algorithm, , 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 eventimes even number is that which is measured by an even number according to an even number.
 9. An eventimes odd number is that which is measured by an even number according to an odd number.
 10. An oddtimes 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]}
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;
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.
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:
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.
 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 selfexplanatory, 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):
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).
Lead In
Recall that
 ... ...
Solve for using the second to last equation and we get:
Because by Euclidean algorithm,
Now let's solve for in the same way:
Now you can see gcd(a, b) is expressed by a linear combination of and . If we continue this process by using the previous equations from the list above, we could get a linear combination of and with representing and representing . 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.
Description
The description of the extended Euclidean algorithm is:
Input: Two nonnegative integers a and b ( ).
Output: d = gcd(a, b) and integers x and y satifying ax + by = d.
Computation:
 If set
 If not, set
 While , do
 Set and return
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:
 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
 From the third equation we get
 .
 Do the same steps for the second equation in the list:
 For the first equation in the list, we get
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 lineartime in the number of digits in b.
Proof
Recall the division equations from the Euclidean algorithm,
 ... ...
We can tell from the equations that the number of steps is with n being the same n as in the division equations. So we want to prove that where k is the number of digits of b.
Notations:
 a and b are integers and we assume a is bigger than b, so .
 The Fibonacci Numbers are 1, 1, 2, 3, 5, 8, 13, ... , where every later number is the sum of the two previous numbers.
 Denote as the nth Fibonacci number (i.e. ).
 All the numbers in the division equations, , are positive integers.
Analyze the division equations and we will have three conclusions:
 couldn't be 0, as otherwise all the remainders would be 0. Hence, .
 We know that . Thus, according to the last equation , should be greater than 1: . Therefore, .
 is an integer, so . Thus, . Since and we have .
Simplify the three conclusions:
According to induction,
...
Therefore,
A theorem about the lower bound of Fibonacci numbers states that for all integers , it is true that where ( the sum of the Golden Ratio and 1).
Therefore,
Thus,
Because b has k digits, . Then
 .
Therefore, 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 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 gcd(), because 2 is definitely a common divisor of two even integers.
 If e is even and v is odd, then gcd(e, f) = gcd(, 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(, the smaller one of e and f). According to Euclidean algorithm, the difference of e and f, which is , could also divide gcd(e, f). And is an integer because the difference of two odd integers is even. Thus, the gcd of 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 ;
Output: g = gcd(u, v)
Inner Computation:
 g = 1.
 While both u and v are even integers, do ; ( "while" means both "if" and "iteration until the condition is no longer satisfied" )
 While , do:
 While u is even, do: ;
 While v is even, do: ;
 ;
 If ; else,
 Return .
Example:
Steiner's algorithm is designed for large numbers, but we only provide an example with small numbers for convenience.
 ;
 Both u and v are even integers.
 ;
 ;
 ; (u and v are not both even now. Move on to the next step.)

 v is even.
 ,
 v is even.

 u is even.
 u is even.

 u is even.
 ( Because u = 0, condition u > 0 is no longer satisfied. Move on to the next step)
 u is even.
 Return
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) ‘‘ Euclidthe creation of mathematics.’’ New York: SpringerVerlag.
[4] Weisstein, Eric W. Euclidean Algorithm. From MathWorldA Wolfram Web Resource. Retrieved from http://mathworld.wolfram.com/EuclideanAlgorithm.html.
[5] Bogomolny, Alexander. Euclid's Algorithm. Retrieved from http://www.cuttheknot.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/historicalprojects/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/dsalgdic/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://wwwusers.cselabs.umn.edu/classes/Fall2009/csci2011/lecture35.pdf.
Future Directions for this Page
 More applets or animations of Euclidean algorithm.
 More pictures if possible.
 Worst case of Euclidean algorithm.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.