# Euclidean Algorithm

(Difference between revisions)
 Revision as of 18:07, 14 July 2011 (edit)← Previous diff Current revision (09:27, 28 June 2012) (edit) (undo) (Moved desciption of Eclid into intro, minor grammar changes) (45 intermediate revisions not shown.) Line 1: Line 1: - {{Image Description + {{Image Description Ready - |ImageName=Euclid's Method to find the gcd + |ImageName=Euclidean Algorithm |Image=EA1.jpg |Image=EA1.jpg |ImageIntro= |ImageIntro= - 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. + 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. - :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. + 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. - + - :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. + |ImageDescElem= |ImageDescElem= - 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 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. - 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. '''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. + 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. Line 33: Line 30: :''Example:'' 3 $\mid$ 6 ; 4 $\mid$ 16 :''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''' 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. ===Precondition === ===Precondition === The Euclidean Algorithm is based on the following theorem: 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$ + :'''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. + :'''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=== ===Description=== Line 73: Line 80: An example will make the Euclidean algorithm clearer. Let's say we want to know the gcd of 168 and 64. 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 + In this case, a = 168, b = 64. Start writing the first equation: - 64 = 1 $\times$ 40 + 24 + 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 40 = 1 $\times$ 24 + 16 Line 94: Line 105: ===Modern Proof=== ===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$ + *'''Proving That It Is A Common Divisor''' - :$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$. + 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 + + {{EquationRef2|Eq. 1}} $a = k_0b + r_1, \quad \quad \quad \quad \quad0 < r_1 < b$ + {{EquationRef2|Eq. 2}} $b = k_1r_1 + r_2 , \quad \quad \quad \quad \quad 0 < r_2 < r_1$ + {{EquationRef2|Eq. 3}} $r_1 = k_2r_2 + r_3, \quad \quad \quad \quad \quad 0 < r_3 < r_2$ + :::... ... + {{EquationRef2|Eq. n-1}}$r_{n-3} = k_{n-2}r_{n-2} + r_{n -1}, \quad \quad 0 < r_{n-2} < r_{n -1}$ + {{EquationRef2|Eq. n}} $r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad \quad 0 < r_{n -1} < r_n$ + {{EquationRef2|Eq. n+1}}$r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad \quad r_n = 0$ + + Based on the last equation {{EquationNote|Eq. n+1}}, we substitute $r_{n -1}$ with $k_nr_n$ in {{EquationNote|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}$. 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$. + From the equation before those two {{EquationNote|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}$. Now we know $r_n \mid r_{n -3}$. Line 114: Line 132: 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. 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: + *'''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 {{EquationNote|Eq. 1}}: - Because $a = k_0b + r_1$ + We know that $a = k_0b + r_1$. Thus, - Therefore $r_1 = a - k_0b = dm - k_0 dn = (m - k_0 n) d$ (substitute dm for a and dn for b) + + $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$. Therefore, $d \mid r_1$. Let $r_1 = d_1 d$. - Consider the second equation. Solve for $r_2$ in the same way. + Consider the second equation {{EquationNote|Eq. 2}}. 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$ + We know that $b = k_1r_1 + r_2$. Thus, - Thus, $d \mid r_2$ + + $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, 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. + Continuing the process until we reach the last equation {{EquationNote|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. Line 152: Line 179: :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. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. :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. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. - '' NOTES: '' + ''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 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. Line 159: Line 186: - ''' Proposition 1.''' + ''' 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.'' :''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.'' Line 183: Line 210: :Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. [VII.Def.12] Q.E.D. :Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. [VII.Def.12] Q.E.D. - ''NOTE : '' + ''Editor's Note : '' - Here is a translation of Proposition 1. + 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: Recall a > b. Write Euclid's proof in equations and we will get: :$a = kb + r, \quad 0 < r < b$ :$a = kb + r, \quad 0 < r < b$ :$b = qr + t, \quad 0 < t < r$ :$b = qr + t, \quad 0 < t < r$ - :$r = lt + \color{Red}1, \quad 1 < r$ + :$r = lt + {\color{Red}1}, \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 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. - 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 without any remainder because e is greater than 1. Therefore, a and b are prime to each other. - + '''Proposition 2.''' (See Image 2) - '''Proposition 2.''' + :''Given two numbers not prime to one another, to find their greatest common measure.'' :''Given two numbers not prime to one another, to find their greatest common measure.'' Line 235: Line 262: PORISM. From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. Q.E.D PORISM. From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication. Q.E.D - '' NOTE : '' + ‘’Editor's Note: '' Prop.2 is pretty self-explanatory, proved in a similar way as Prop.1. 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.''' + '''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= =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). + 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 a,b are bigger than gcd(a, b) more often than not. + $ax +by = gcd(a, b).$ - Recall that + 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). - :$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: + ==Description== - :$r_n = r_{n-2} - k_{n-1}r_{n-1}$ + - :{{EquationRef2|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: + The description of the extended Euclidean algorithm is: - :{{EquationRef2|Eq. 2}}$r_{n -1} = r_{n -3} - k_{n-2}r_{n-2}$ + - + - Substitute {{EquationNote|Eq. 2}} into {{EquationNote|Eq. 1}}: + - + - + - 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$). '''Input:''' Two non-negative integers a and b ( $a \leqslant b$). Line 287: Line 288: '''Computation:''' '''Computation:''' - *If b = 0, set d = a, x = 1, y = 0, and return(d, x, y). + *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$ *If not, set$x_2 = 1, x_1 = 0, y_2 = 0, y_1 = 1$ - *While b > 0, do + *While $b > 0$, do :$q = floor(\frac{a}{b}), r = a - qb, x = x_2 - qx_1, y = y_2 - q y_1.$ :$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.$ :$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). + *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: 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.'' ''Solve for integers x and y such that 168x + 64y = 8.'' - *Apply Euclidean algorithm to compute gcd(168, 64): + *Apply Euclidean algorithm to compute gcd(168, 64), and we have a list of the following equations: + + :$168 = 2 \times 64 + 40$ - :168 = 2 $\times$ 64 + 40 + :$64 = 1 \times 40 + 24$ - :64 = 1 $\times$ 40 + 24 + :$40 = 1 \times 24 + 16$ - :40 = 1 $\times$ 24 + 16 + :$24 = 1 \times 16 + 8$ - :24 = 1 $\times$ 16 + 8 + :$16 = 2 \times 8 + 0$ - :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: *Use the extended Euclidean algorithm to get x and y: - From the fourth equation we get {{EquationRef2|Eq. 3}}8 = 24 - 1 $\times$ 16. + :From the fourth equation we get {{EquationRef2|Eq. 6}} $8 = 24 - 1 \times 16.$ - From the third equation we get {{EquationRef2|Eq. 4}}16 = 40 - 1 $\times$ 24. + :From the third equation we get {{EquationRef2|Eq. 7}} $16 = 40 - 1 \times 24$. - *Substitute {{EquationNote|Eq. 4}} into {{EquationNote|Eq. 3}}: + *Substitute {{EquationNote|Eq. 7}} into {{EquationNote|Eq. 6}}: - :8 = 24 - 1 $\times$ (40 - 1 $\times$ 24) + :$8 = 24 - 1 \times (40 - 1 \times 24)$ - :8 = 24 - 1 $\times$40 + 1$\times$24 + :$8 = 24 - 1 \times 40 + 1 \times 24$ - :8 = 2$\times$24 - 1$\times$40 + :$8 = 2 \times 24 - 1 \times 40$ - *Do the same steps for the second equation: 24 = 64 - 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 - 1 \times 40) - 1\times 40$ - :8 = 2$\times$64 - 3$\times$ 40 + :$8 = 2\times 64 - 3\times 40$ - From the first equation we get 40 = 168 - 2$\times$64 + :For the first equation in the list, we get $40 = 168 - 2 \times 64$ - Therefore, 8 = 2$\times$64 - 3$\times$ (168 - 2$\times$64) + :$8 = 2\times 64 - 3 \times (168 - 2 \times 64)$ - :\therefore 8 = -3$\times$168 + 8$\times$64 + :$8 = -3 \times 168 + 8 \times 64$ - :$\therefore$x = -3, y = 8 + :$\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, + :{{EquationRef2|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: + :{{EquationRef2|Eq. 5}}$r_{n -1} = r_{n -3} - k_{n-2}r_{n-2}$ + + Substitute {{EquationNote|Eq. 5}} into {{EquationNote|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. ''' - '''The Euclidean algorithm makes it elegantly easy to compute the two Bézout's coefficients. ''' =Efficiency= =Efficiency= + + How efficient could Euclidean algorithm be? Is it always perfect? Does Euclidean algorithm have shortcomings? ==Number of Steps - Lamé's Theorem== ==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. + 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:''' + '''Proof''' Recall the division equations from the Euclidean algorithm, Recall the division equations from the Euclidean algorithm, Line 355: Line 389: :$r_{n -1} = k_nr_n, \quad r_{n+1} = 0$ :$r_{n -1} = k_nr_n, \quad r_{n+1} = 0$ - The number of steps is n+1. + 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: + # 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$). + #All the numbers in the division equations, $a, b, r_n, k_n$, are positive integers. - 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. + 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$. *$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$. + *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$. - *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$. + *$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$. - So far, we have three conclusions: + Simplify the three conclusions: :$r_n \geqslant 1 = F_2$ :$r_n \geqslant 1 = F_2$ Line 379: Line 419: Therefore, $b \geqslant 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). + 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$ 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}$ + Thus, $\log_{10} b > \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 + + Because b has k digits, $k > \log_{10} b$. Then + :$k > \log_{10} b > \frac{n}{5}$ :$k > \frac{n}{5}$ :$k > \frac{n}{5}$ :$5k > n$ :$5k > n$ :$5k +1 > n + 1$ :$5k +1 > n + 1$ :$5k \geqslant n + 1$ :$5k \geqslant n + 1$ + :$n + 1 \leqslant 5k$. - 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. + 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== ==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. + 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. + '''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. - The algorithm has the following conclusions: + 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. + *$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 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 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. + + *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. - The description of Stein's algorithm: + *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. - '''Input:'''$u, v ( 0 < u \leqslant v )$; - '''Output: ''' g = gcd(u, v) + 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: ''' '''Inner Computation: ''' #g = 1. #g = 1. - # While both u and v are even integers, do $u = \frac{u}{2}, v = \frac{v}{2}, g = 2g$. + # 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" '') # While $u > 0$, do: # While $u > 0$, do: - ## While u is even, do: $u =\frac{u}{2}$. + ## While u is even, do: $u =\frac{u}{2}$; - ## While v is even, do: $v = \frac{v}{2}$. + ## While v is even, do: $v = \frac{v}{2}$; - ## $t = \frac{\left\vert u - v \right\vert }{2}$. + ## $t = \frac{\left\vert u - v \right\vert }{2}$; - ## If $u \leqslant v$, u = t; else, v = t. + ## If $u \leqslant v , u = t$; else, $v = t;$ - # Return ($g \cdot v$) + # Return $g \cdot v$. - '''Example:''' ''$u=168, v=64$'' + '''Example:''' - #$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$; + + ''Steiner's algorithm is designed for large numbers, but we only provide an example with small numbers for convenience.'' + + :$u=168, v=64$ + + # $g = 1$; + # Both u and v are even integers. + ##$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$; (''u and v are not both even now. Move on to the next step.'') # $u = 21 > 0;$ # $u = 21 > 0;$ - ## $v = \frac{8}{2} = 4; v = \frac{4}{2} = 2; v = \frac{2}{2} = 1;$ + ## v is even. + ###$v = \frac{8}{2} = 4;$ + ###$v = \frac{4}{2} = 2;$ + ###$v = \frac{2}{2} = 1;$ ## $t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10$, ## $t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10$, - ## $\because u = 21 > 1 = v, \therefore u = t =10;$ + ## $u = 21 > 1 = v, \therefore u = t =10;$ # $u = 10 > 0, v =1;$ # $u = 10 > 0, v =1;$ - ## $u = \frac{10}{2} = 5;$ + ## u is even. + ###$u = \frac{10}{2} = 5;$ ## $t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2,$ ## $t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2,$ - ## $\because u = 5 > 1 = v, \therefore u = t = 2;$ + ## $u = 5 > 1 = v, \therefore u = t = 2;$ # $u = 2 > 0, v =1;$ # $u = 2 > 0, v =1;$ - ## $u = \frac{2}{2} = 1;$ + ## u is even. + ###$u = \frac{2}{2} = 1;$ ## $t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0,$ ## $t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0,$ - ## $\because u = 2 > 1 = v, \therefore u = t = 0;$ + ## $u = 2 > 1 = v, \therefore u = t = 0;$ ('' Because u = 0, condition u > 0 is no longer satisfied. Move on to the next step'') - # $g = g \cdot v = 8 \times 1 = 8.$ + # 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. + 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. |WhyInteresting= |WhyInteresting= - 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. + 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. Line 494: Line 552: #Worst case of Euclidean algorithm. #Worst case of Euclidean algorithm. - |InProgress=Yes + |InProgress=No }} }}

## Current revision

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

• ' [...]

## 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.[1]

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. [1] [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. [1] 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$.
$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.

# References

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

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

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

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

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

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