# Euclidean Algorithm

### From Math Images

(Difference between revisions)
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|----------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Current revision (10:27, 28 June 2012) (edit) (undo) (Moved desciption of Eclid into intro, minor grammar changes) |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| (33 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 <balloon title="An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations.">algorithm</balloon>  (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 <balloon title="An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations.">algorithm</balloon>  (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 <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.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | ===Precondition ===                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |                                                                                                                    | ===Precondition ===                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        | The Euclidean Algorithm is based on the following theorem:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |                                                                                                                    | The Euclidean Algorithm is based on the following theorem:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
| -                                      | :'''Theorem:''' <math> gcd(a, b) = gcd(b,~ a~mod~b) </math> where <math>a > b</math> and <math>a~ mod~ b ~\ne 0 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                | +                                                                                                                  | :'''Theorem:''' <math> gcd(a, b) = gcd(b,~ a~mod~b) </math> where <math>a > b</math> and <math>a~ mod~ b ~\ne 0 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
| -                                      | :'''Proof:''' Since <math>a > b</math>, <math>a</math> could be denoted as <math>a = kb + r</math> with <math>0 \leqslant r < b </math>. Then <math>r = a~mod~b</math>. Assume <math>d</math> is a common divisor of <math>a</math> and <math>b</math>, thus  <math>d \mid a , d\mid b</math>, or we could write them as <math>a= q_1 d, b = q_2 d. </math> Because of <math>r = a - kb</math>, <math> r = q_1 d - k q_2 d = (q_1 - k q_2) d </math> and we will get<math>d \mid r </math>. Therefore <math>d</math> is also a common divisor of <math>(b, r) = (b, a~mod~b)</math>. Hence, the common divisors of <math>(a, b)</math> and <math>(b, a~mod~b)</math> are the same. In other words, <math>(a, b)</math> and <math>(b, a~mod~b)</math> have the same common divisors, and so they have the same greatest common divisor. | +                                                                                                                  | :'''Proof:'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Since <math>a > b</math>, <math>a</math> could be denoted as <math>a = kb + r</math> with <math>0 \leqslant r < b </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Then the remainder <math>r = a~mod~b</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Assume <math>d</math> is a common divisor of <math>a</math> and <math>b</math>, thus  <math>d \mid a , d\mid b</math>, or we could write them as <math>a= q_1 d, b = q_2 d. </math>                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Because <math>r = a - kb</math>,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::<math> r = q_1 d - k q_2 d = (q_1 - k q_2) d </math>, so we know <math>d \mid r </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Therefore <math>d</math> is also a common divisor of <math>(b, r) = (b, a~mod~b)</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::Hence, the common divisors of <math>(a, b)</math> and <math>(b, a~mod~b)</math> are the same.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ::In other words, <math>(a, b)</math> and <math>(b, a~mod~b)</math> 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 <math>\times</math> 64 + 40                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    | +                                                                                                                  | In this case, a = 168, b = 64. Start writing the first equation:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | 64 = 1 <math>\times</math> 40 + 24                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     | +                                                                                                                  | 168 = 2 <math>\times</math> 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 <math>\times</math> 40 + 24                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :'' (Get the remainder 40 from the last equation. <math>r_1 = 40</math>. Use it as the quotient for this second equation. By analog, find the coefficient for 40 and the remainder.) ''                                                                                                                                                                                                                                                                                                                                                                                                            |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | 40 = 1 <math>\times</math> 24 + 16                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |                                                                                                                    | 40 = 1 <math>\times</math> 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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>a = k_0b + r_1, \quad a\,\bmod\,b = r_1, \quad 0 < r_1 < b</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               | +                                                                                                                  | *'''Proving That It Is A Common Divisor'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
| -                                      | :<math>b = k_1r_1 + r_2 , \quad b\,\bmod\,r_1 = r_2, \quad 0 < r_2 < r_1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_1 = k_2r_2 + r_3, \quad r_1\,\bmod\,r_2 = r_3, \quad 0 < r_3 < r_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_2 = k_3r_3 + r_4, \quad r_2\,\bmod\,r_3 = r_4, \quad 0 < r_4 < r_3</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :... ...                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>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</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_{n -1} = k_nr_n, \quad\quad\quad\quad r_{n- 1}\,\bmod\, \quad r_n = 0</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Based on the last two equations, we substitute <math>r_{n -1} </math> with <math>k_nr_n</math> in the last to second equation such that <math>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 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                | +                                                                                                                  | 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}}  <math>a = k_0b + r_1, \quad \quad \quad \quad \quad0 < r_1 < b</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | {{EquationRef2|Eq. 2}}  <math>b = k_1r_1 + r_2 , \quad \quad \quad \quad \quad 0 < r_2 < r_1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | {{EquationRef2|Eq. 3}}  <math>r_1 = k_2r_2 + r_3, \quad \quad \quad \quad \quad 0 < r_3 < r_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :::... ...                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | {{EquationRef2|Eq. n-1}}<math>r_{n-3} = k_{n-2}r_{n-2} + r_{n -1}, \quad \quad 0 < r_{n-2} < r_{n -1} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | {{EquationRef2|Eq. n}}  <math>r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad \quad 0 < r_{n -1} < r_n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | {{EquationRef2|Eq. n+1}}<math>r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad \quad r_n = 0</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Based on the last equation {{EquationNote|Eq. n+1}}, we substitute <math>r_{n -1} </math> with <math>k_nr_n</math> in {{EquationNote|Eq. n}} such that                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | <math>r_{n -2} = k_{n -1}r_{n -1} + r_n = k_{n -1}k_nr_n + r_n </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | <math>r_{n-2} = (k_{n -1}k_n + 1) r_n </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Thus we have <math>r_n \mid r_{n -2} </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |                                                                                                                    | Thus we have <math>r_n \mid r_{n -2} </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | From the equation before those two, we repeat the steps we did just now: <math>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 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  | From the equation before those two {{EquationNote|Eq. n-1}}, we repeat the steps we did just now: <math>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 </math>.                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Now we know <math>r_n \mid r_{n -3}</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |                                                                                                                    | Now we know <math>r_n \mid r_{n -3}</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
| Line 114:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 132:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Continue this process and we will find that <math>r_n \mid a, r_n \mid b</math>, so <math>r_n </math>, the number we get from Euclidean algorithm, is indeed a common divisor of a and b.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |                                                                                                                    | Continue this process and we will find that <math>r_n \mid a, r_n \mid b</math>, so <math>r_n </math>, the number we get from Euclidean algorithm, is indeed a common divisor of a and b.                                                                                                                                                                                                                                                                                                                                                                                                          |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Second, we need to show that <math>r_n</math> is the greatest among all the common divisors of a and b. To show that <math>r_n</math> 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 <math>r_n</math> is the greatest among all the common divisors of a and b. To show that <math>r_n</math> 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}}: |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | We know that <math>a = k_0b + r_1 </math>. Thus,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | <math>r_1 = a - k_0b = dm - k_0 dn</math>, and                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Because <math>a = k_0b + r_1 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   | +                                                                                                                  | <math>r_1  = (m - k_0 n) d</math> (substitute dm for a and dn for b).                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
| -                                      | Therefore <math>r_1 = a - k_0b = dm - k_0 dn = (m - k_0 n) d</math> (substitute dm for a and dn for b)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Therefore, <math>d \mid r_1 </math>. Let <math> r_1 = d_1 d</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |                                                                                                                    | Therefore, <math>d \mid r_1 </math>. Let <math> r_1 = d_1 d</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Consider the second equation. Solve for <math>r_2</math> in the same way.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              | +                                                                                                                  | Consider the second equation {{EquationNote|Eq. 2}}. Solve for <math>r_2</math> in the same way.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
| -                                      | Because <math>b = k_1r_1 + r_2 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Therefore <math> r_2 = b - k_1r_1= dn - k_1d_1 d = (n - k_1d_1) d</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Thus, <math>d \mid r_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Continuing the process until we reach the last equation, we will get <math>d \mid r_n </math>. Since we pick d to represent any possible common divisor of a and b except <math>r_n, d \mid r_n</math> means that <math>r_n</math> divides any other common divisor of a and b, meaning that <math>r_n</math> must be greater than all the other common divisors. Therefore, the number we get from the Euclidean Algorithm, <math>r_n</math>, is indeed the greatest common divisor of a and b.                                                                                                                                                                                                                                                                                                                                       | +                                                                                                                  | We know that <math>b = k_1r_1 + r_2 </math>. Thus,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | <math> r_2 = b - k_1r_1= dn - k_1d_1 d </math>, and                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | <math>r_2 = (n - k_1d_1) d</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Therefore, <math>d \mid r_2</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Continuing the process until we reach the last equation {{EquationNote|Eq. n}}, we will get <math>d \mid r_n </math>. Since we pick d to represent any possible common divisor of a and b except <math>r_n, d \mid r_n</math> means that <math>r_n</math> divides any other common divisor of a and b, meaning that <math>r_n</math> must be greater than all the other common divisors. Therefore, the number we get from the Euclidean Algorithm, <math>r_n</math>, 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.<ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    | :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.<ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref>                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | '' NOTE: ''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            | +                                                                                                                  | ''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 183:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 210:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | :Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. <ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref> [VII.Def.12] Q.E.D.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |                                                                                                                    | :Therefore no number will measure the numbers AB, CD; therefore AB, CD are prime to one another. <ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref> [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?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |                                                                                                                    | Euclid wants to show that a and b must be prime to each other if we get 1 left instead of 0. Why?                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |
| 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. <ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref> Q.E.D                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    | PORISM. From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. <ref name=BookVII> Health T.L.. (1956). The Thirteen Books of Euclid's Elements. New York: Dover Publication.</ref> 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.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
| Line 245:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 272:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | =Extended Euclidean Algorithm=                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |                                                                                                                    | =Extended Euclidean Algorithm=                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Expand the Euclidean algorithm and you will be able to solve <balloon title="In number theory, Bézout's identity for two integers a,b is an expression ax + by = d, where x and y are integers (called Bézout's coefficients for (a, b)) and d is a common divisor of a and b." >'''Bézout's identity'''</balloon> for x and y where d = gcd(a, b):                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    | +                                                                                                                  | Expand the Euclidean algorithm and you will be able to solve '''<balloon title="In number theory, Bézout's identity for two integers a,b is an expression ax + by = d, where x and y are integers (called Bézout's coefficients for (a, b)) and d is a common divisor of a and b." >Bézout's identity</balloon>''' for x and y where d = gcd(a, b):                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | <math>ax +by = gcd(a, b).  </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |                                                                                                                    | <math>ax +by = gcd(a, b).  </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | 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).                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    | 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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>a = k_0b + r_1, \quad 0 < r_1 < b</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :... ...                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>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</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_{n -1} = k_nr_n, \quad\quad\quad\quad r_{n- 1}\,\bmod\, \quad r_n = 0</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Solve for <math>r_n</math> using the second to last equation and we get:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math>r_n = r_{n-2} - k_{n-1}r_{n-1}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Because <math>r_n = gcd(a, b)</math> by Euclidean algorithm,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :{{EquationRef2|Eq. 1}}<math>gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Now let's solve for <math>r_{n-1} </math> in the same way:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :{{EquationRef2|Eq. 2}}<math>r_{n -1} = r_{n -3} - k_{n-2}r_{n-2}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Substitute {{EquationNote|Eq. 2}} into {{EquationNote|Eq. 1}}:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math> gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math> gcd(a, b) = r_{n -2} - k_{n -1}(r_{n -3} - k_{n-2}r_{n-2}) </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math> gcd(a, b) = r_{n -2} - k_{n -1}r_{n -3} + k_{n-1}k_{n-2}r_{n-2} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | :<math> {\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}}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Now you can see gcd(a, b) is expressed by a linear combination of <math>r_{n-2}</math> and <math>r_{n-3}</math>. If we continue this process by using the previous equations from the list above, we could get a linear combination of <math>r_{n-3}</math> and <math>r_{n-4}</math> with <math>r_{n-3}</math> representing <math>r_{n-2}</math> and <math>r_{n-4}</math> representing <math>r_{n-3}</math>. 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==                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    | ==Description==                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| Line 288:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 288:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | '''Computation:'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |                                                                                                                    | '''Computation:'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | *If <math>b = 0,</math> set <math>d = a, x = 1, y = 0,</ math> and return <math>(d, x, y).</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      | +                                                                                                                  | *If <math>b = 0,</math> set <math>d = a, x = 1, y = 0,</math> and return <math>(d, x, y).</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
|                                        | *If not, set<math> x_2 = 1, x_1 = 0, y_2 = 0, y_1 = 1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    | *If not, set<math> x_2 = 1, x_1 = 0, y_2 = 0, y_1 = 1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        | *While <math>b > 0</math>, do                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |                                                                                                                    | *While <math>b > 0</math>, do                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
| Line 317:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 317:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | *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}} <math>8 = 24 - 1 \times 16. </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            | +                                                                                                                  | :From the fourth equation we get {{EquationRef2|Eq. 6}} <math>8 = 24 - 1 \times 16. </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
| -                                      | :From the third equation we get {{EquationRef2|Eq. 4}} <math>16 = 40 - 1 \times 24 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            | +                                                                                                                  | :From the third equation we get {{EquationRef2|Eq. 7}} <math>16 = 40 - 1 \times 24 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | *Substitute {{EquationNote|Eq. 4}} into {{EquationNote|Eq. 3}}:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | *Substitute {{EquationNote|Eq. 7}} into {{EquationNote|Eq. 6}}:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | :<math>8 = 24 - 1 \times (40 - 1 \times 24) </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |                                                                                                                    | :<math>8 = 24 - 1 \times (40 - 1 \times 24) </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
| Line 337:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 337:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | :<math>\therefore x = -3, y = 8 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    | :<math>\therefore x = -3, y = 8 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ==Proof==                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Recall that                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>a = k_0b + r_1, \quad 0 < r_1 < b</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :... ...                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad 0 < r_{n -1} < r_n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad r_n = 0</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Solve for <math>r_n</math> using the second to last equation and we get:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>r_n = r_{n-2} - k_{n-1}r_{n-1}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Because <math>r_n = gcd(a, b)</math> by Euclidean algorithm,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :{{EquationRef2|Eq. 4}}<math>gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Now let's solve for <math>r_{n-1} </math> in the same way:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :{{EquationRef2|Eq. 5}}<math>r_{n -1} = r_{n -3} - k_{n-2}r_{n-2}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Substitute {{EquationNote|Eq. 5}} into {{EquationNote|Eq. 4}}:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math> gcd(a, b) = r_{n -2} - k_{n -1}r_{n-1} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math> gcd(a, b) = r_{n -2} - k_{n -1}(r_{n -3} - k_{n-2}r_{n-2}) </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math> gcd(a, b) = r_{n -2} - k_{n -1}r_{n -3} + k_{n-1}k_{n-2}r_{n-2} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math> {\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}}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Now you can see gcd(a, b) is expressed by a linear combination of <math>r_{n-2}</math> and <math>r_{n-3}</math>. If we continue this process by using the previous equations from the list above, we could get a linear combination of <math>r_{n-3}</math> and <math>r_{n-4}</math> with <math>r_{n-3}</math> representing <math>r_{n-2}</math> and <math>r_{n-4}</math> representing <math>r_{n-3}</math>. 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. '''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |                                                                                                                    | '''Euclidean algorithm and extended Euclidean algorithm makes it elegantly easy to compute the two Bézout's coefficients. '''                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | =Efficiency=                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    | =Efficiency=                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
| Line 349:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 377:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | 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.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |                                                                                                                    | 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:'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           | +                                                                                                                  | <big>'''Proof'''</big>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Recall the division equations from the Euclidean algorithm,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |                                                                                                                    | Recall the division equations from the Euclidean algorithm,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
| Line 369:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 397:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | #All the numbers in the division equations, <math>a, b, r_n, k_n</math>, are positive integers.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    | #All the numbers in the division equations, <math>a, b, r_n, k_n</math>, are positive integers.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Then we will have three conclusions:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   | +                                                                                                                  | Analyze the division equations and we will have three conclusions:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | *<math>r_n</math> couldn't be 0, as otherwise all the remainders would be 0. Hence, <math>r_n \geqslant 1 = F_2</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    | *<math>r_n</math> couldn't be 0, as otherwise all the remainders would be 0. Hence, <math>r_n \geqslant 1 = F_2</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
| Line 377:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 405:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | *<math>k_{n -1}</math> is an integer, so <math>k_{n -1} \geqslant 1 </math>. Thus, <math>r_{n -2} \geqslant r_n + r_{n -1} </math>. Since <math>r_{n -1} \geqslant  F_3 </math> and <math>r_{n} \geqslant  F_2, </math> we have <math> r_{n-2} \geqslant F_2 + F_3 = F_4 </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |                                                                                                                    | *<math>k_{n -1}</math> is an integer, so <math>k_{n -1} \geqslant 1 </math>. Thus, <math>r_{n -2} \geqslant r_n + r_{n -1} </math>. Since <math>r_{n -1} \geqslant  F_3 </math> and <math>r_{n} \geqslant  F_2, </math> we have <math> r_{n-2} \geqslant F_2 + F_3 = F_4 </math>.                                                                                                                                                                                                                                                                                                                  |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | To simplify the three conclusions:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     | +                                                                                                                  | Simplify the three conclusions:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | :<math>r_n \geqslant 1 = F_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |                                                                                                                    | :<math>r_n \geqslant 1 = F_2</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |
| Line 391:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | Line 419:                                                                                                          |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Therefore, <math> b \geqslant F_{n + 2}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |                                                                                                                    | Therefore, <math> b \geqslant F_{n + 2}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | A theorem about the lower bound of Fibonacci numbers states that for all integers <math>n \geqslant 3, it is true that F_n > \alpha ^{n -2}, </math> where <math>\alpha = \frac{1+\sqrt{5}}{2} \approx 1.61803</math> (the sum of the [[Golden Ratio]] and 1).                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         | +                                                                                                                  | A theorem about the lower bound of Fibonacci numbers states that for all integers <math>n \geqslant 3</math>, it is true that <math> F_n > \alpha ^{n -2} </math> where <math>\alpha = \frac{1+\sqrt{5}}{2} \approx 1.61803</math> ( the sum of the [[Golden Ratio]] and 1).                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | Therefore, <math>b \geqslant F_{n+2} > \alpha ^n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    | Therefore, <math>b \geqslant F_{n+2} > \alpha ^n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Thus, <math>\log_{10} b \geqslant \log_{10} \alpha ^n = n \log_{10} \alpha \approx n 0.208 \approx \frac{n}{5}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  | +                                                                                                                  | Thus, <math>\log_{10} b > \log_{10} \alpha ^n = n \log_{10} \alpha \approx n~0.208 \approx \frac{n}{5}</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
| -                                      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Assume b has k digits, so <math>k > \log_{10} b</math>. Then                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | Because b has k digits, <math>k > \log_{10} b</math>. Then                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math> k > \log_{10} b > \frac{n}{5} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        | :<math> k > \frac{n}{5} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    | :<math> k > \frac{n}{5} </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | :<math> 5k > n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    | :<math> 5k > n</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        | :<math>5k +1 > n + 1 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    | :<math>5k +1 > n + 1 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        | :<math>5k \geqslant n + 1 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |                                                                                                                    | :<math>5k \geqslant n + 1 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>n + 1 \leqslant 5k </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | Therefore, the number of steps <math>n + 1 \leqslant 5k </math>. 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 (<math>n + 1</math>) required by Euclidean algorithm for gcd(a,b) is no more than five times the number of digits of b (<math>5k</math>).                                                                                                                                                                                                                                                                                                                                                                                                                           |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | ==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.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       | +                                                                                                                  | *<math>gcd(m, 0) = m, gcd(0, m) = m. </math>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(<math>\frac{e}{2}, \frac{f}{2}</math>), because 2 is definitely a common divisor of two even integers.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      | +                                                                                                                  | *If e and f are both even integers, then <math>gcd(e, f) = 2 \cdot gcd\left ( \frac{e}{2}, \frac{f}{2} \right )</math>, because 2 is definitely a common divisor of two even integers.                                                                                                                                                                                                                                                                                                                                                                                                             |
| -                                      | *If e is even and v is odd, then gcd(e, f) = gcd(<math>\frac{e}{2}</math>, 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(<math>\frac{|e-f|}{2}</math>, 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 <math>gcd(e, f) = gcd \left ( \frac{e}{2}, f \right ) </math>, 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 <math> gcd(e, f) = gcd\left ( \frac{|e-f|}{2}, \mbox{the smaller one of e and f} \right ) </math>.  According to Euclidean algorithm, the difference of e and f, which is <math>|e-f|</math>, could also divide <math>gcd(e, f)</math>. And <math>\frac{|e-f|}{2}</math> is an integer because the difference of two odd integers is even. Thus, the gcd of <math>\frac{|e-f|}{2}</math> and the smaller one of e is the gcd of e and f.                                                                                                                               |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | '''Input:'''<math> u, v  ( 0 < u \leqslant v ) </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | '''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<math> u, v</math> with <math> 0 < u \leqslant v </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | '''Output: ''' <math>g = gcd(u, v) </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | '''Inner Computation: '''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |                                                                                                                    | '''Inner Computation: '''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | #g = 1.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                |                                                                                                                    | #g = 1.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
| -                                      | # While both u and v are even integers, do <math> u = \frac{u}{2}, v = \frac{v}{2}, g = 2g </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    | +                                                                                                                  | # While both u and v are even integers, do <math> u = \frac{u}{2}, v = \frac{v}{2}, g = 2g </math>;  ('' "while" means both "if" and "iteration until the condition is no longer satisfied" '')                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        | # While <math>u > 0 </math>, do:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |                                                                                                                    | # While <math>u > 0 </math>, do:                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
| -                                      | ## While u is even, do: <math> u =\frac{u}{2} </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  | ## While u is even, do: <math> u =\frac{u}{2} </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
| -                                      | ## While v is even, do: <math> v = \frac{v}{2}</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  | ## While v is even, do: <math> v = \frac{v}{2}</math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
| -                                      | ## <math> t = \frac{\left\vert u - v \right\vert }{2}</math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          | +                                                                                                                  | ## <math> t = \frac{\left\vert u - v \right\vert }{2}</math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
| -                                      | ## If <math> u  \leqslant v </math>, u = t; else, v = t.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               | +                                                                                                                  | ## If <math> u  \leqslant v , u = t </math>; else, <math>v = t;</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
| -                                      | # Return (<math>g \cdot v </math>)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     | +                                                                                                                  | # Return <math>g \cdot v </math>.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | '''Example:'''  ''<math>u=168, v=64 </math>''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          | +                                                                                                                  | '''Example:'''                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |
| -                                      | #<math>u = \frac{168}{2} = 84, v = \frac{64}{2} = 32, g = 2 </math>; <math> u = \frac{84}{2} = 42, v = \frac{32}{2} = 16, g = 4 </math>; <math> u = \frac{42}{2} = 21, v = \frac{16}{2} = 8, g =8 </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ''Steiner's algorithm is designed for large numbers, but we only provide an example with small numbers for convenience.''                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | :<math>u=168, v=64 </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | # <math> g = 1</math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | # Both u and v are even integers.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ##<math>u = \frac{168}{2} = 84, v = \frac{64}{2} = 32, g = 2 </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ##<math> u = \frac{84}{2} = 42, v = \frac{32}{2} = 16, g = 4 </math>;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ##<math> u = \frac{42}{2} = 21, v = \frac{16}{2} = 8, g =8 </math>; (''u and v are not both even now. Move on to the next step.'')                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
|                                        | # <math> u = 21 > 0; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |                                                                                                                    | # <math> u = 21 > 0; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       |
| -                                      | ## <math> v = \frac{8}{2} = 4; v = \frac{4}{2} = 2; v = \frac{2}{2} = 1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       | +                                                                                                                  | ## v is even.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ###<math> v = \frac{8}{2} = 4; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ###<math> v = \frac{4}{2} = 2; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ###<math> v = \frac{2}{2} = 1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        | ## <math> t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10 </math>,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               |                                                                                                                    | ## <math> t =\frac{\left\vert 21- 1 \right\vert}{2} = \frac{20}{2} = 10; t = 10 </math>,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           |
| -                                      | ## <math>\because u = 21 > 1 = v, \therefore u = t =10; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ## <math>u = 21 > 1 = v, \therefore u = t =10; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        | # <math> u = 10 > 0, v =1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |                                                                                                                    | # <math> u = 10 > 0, v =1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |
| -                                      | ## <math>u = \frac{10}{2} = 5; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 | +                                                                                                                  | ## u is even.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ###<math>u = \frac{10}{2} = 5; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
|                                        | ## <math> t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2, </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |                                                                                                                    | ## <math> t = \frac{\left\vert 5- 1 \right\vert}{2} = \frac{4}{2} = 2; t = 2, </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
| -                                      | ## <math> \because u = 5 > 1 = v, \therefore u = t = 2;</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         | +                                                                                                                  | ## <math> u = 5 > 1 = v, \therefore u = t = 2;</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        | # <math> u = 2 > 0, v =1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |                                                                                                                    | # <math> u = 2 > 0, v =1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  |
| -                                      | ## <math>u = \frac{2}{2} = 1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  | +                                                                                                                  | ## u is even.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  | ###<math>u = \frac{2}{2} = 1; </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              |
|                                        | ## <math> t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0, </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 |                                                                                                                    | ## <math> t = \frac{\left\vert 1 - 1 \right\vert}{2} = \frac{0}{2} = 0; t = 0, </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             |
| -                                      | ## <math> \because u = 2 > 1 = v, \therefore u = t = 0;</math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         | +                                                                                                                  | ## <math>u = 2 > 1 = v, \therefore u = t = 0;</math> ('' Because u = 0, condition u > 0 is no longer satisfied. Move on to the next step'')                                                                                                                                                                                                                                                                                                                                                                                                                                                        |
| -                                      | # <math> g = g \cdot v = 8 \times 1 = 8. </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       | +                                                                                                                  | # Return <math> g = g \cdot v = 8 \times 1 = 8. </math>                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | +                                                                                                                  |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
|                                        |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        |                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |
| -                                      | 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 506:                              |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        | 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
[Click to view A More Mathematical Explanation]

## The Description of Euclidean Algorithm

### Mathematical definitions and their abbreviations

• ' [...]

[Click to hide A More Mathematical Explanation]

## The Description of Euclidean Algorithm

### Mathematical definitions and their abbreviations

• a mod b is the remainder when a is divided by b (where mod = modulo).
Example: 7 mod 4 = 3; 4 mod 2 = 0; 5 mod 9 = 5
• a $\mid$ b means a divides b exactly or b is divided by a without any remainder.
Example: 3 $\mid$ 6 ; 4 $\mid$ 16
• gcd means the greatest common divisor, also called the greatest common factor (gcf), the highest common factor (hcf), and the greatest common measure (gcm).
• gcd(a, b) means the gcd of two positive integers a and b; (a, b) is another notation for gcd(a, b).

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

### Precondition

The Euclidean Algorithm is based on the following theorem:

Theorem: $gcd(a, b) = gcd(b,~ a~mod~b)$ where $a > b$ and $a~ mod~ b ~\ne 0$.
Proof:
Since $a > b$, $a$ could be denoted as $a = kb + r$ with $0 \leqslant r < b$.
Then the remainder $r = a~mod~b$.
Assume $d$ is a common divisor of $a$ and $b$, thus $d \mid a , d\mid b$, or we could write them as $a= q_1 d, b = q_2 d.$
Because $r = a - kb$,
$r = q_1 d - k q_2 d = (q_1 - k q_2) d$, so we know $d \mid r$.
Therefore $d$ is also a common divisor of $(b, r) = (b, a~mod~b)$.
Hence, the common divisors of $(a, b)$ and $(b, a~mod~b)$ are the same.
In other words, $(a, b)$ and $(b, a~mod~b)$ have the same common divisors, and so they have the same greatest common divisor.

### Description

The description of the Euclidean algorithm is as follows:

• Input two positive integers, a,b (a > b)
• Output g, the gcd of a, b
• Internal Computation
1. Divide a by b and get the remainder r.
2. If r=0, report b as the gcd of a and b. If r $\ne$0, replace a by b and replace b by r. Go back to the previous step.

The algorithm process is like this:

$a = k_0b + r_1, \quad 0 < r_1 < b$
$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$
$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$
$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$
... ...
$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad 0 < r_{n -1} < r_n$
$r_{n -1} = k_nr_n, \quad\quad\quad\quad r_n = 0$

To sum up,

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

$r_n$ is the gcd of a and b.

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

### Example

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

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

168 = 2 $\times$ 64 + 40

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

64 = 1 $\times$ 40 + 24

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

40 = 1 $\times$ 24 + 16

24 = 1 $\times$ 16 + 8

16 = 2 $\times$ 8

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

Therefore, 8 is the gcd of 168 and 64.

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

## Proof of the Euclidean Algorithm

### Modern Proof

• Proving That It Is A Common Divisor

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

$a = k_0b + r_1, \quad \quad \quad \quad \quad0 < r_1 < b$
$b = k_1r_1 + r_2 , \quad \quad \quad \quad \quad 0 < r_2 < r_1$
$r_1 = k_2r_2 + r_3, \quad \quad \quad \quad \quad 0 < r_3 < r_2$
... ...
$r_{n-3} = k_{n-2}r_{n-2} + r_{n -1}, \quad \quad 0 < r_{n-2} < r_{n -1}$
$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad \quad 0 < r_{n -1} < r_n$
$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
$8 = 24 - 1 \times 16.$
From the third equation we get
$16 = 40 - 1 \times 24$.
• Substitute Eq. 7 into Eq. 6:
$8 = 24 - 1 \times (40 - 1 \times 24)$
$8 = 24 - 1 \times 40 + 1 \times 24$
$8 = 2 \times 24 - 1 \times 40$
• Do the same steps for the second equation in the list: $24 = 64 - 1 \times 40$
$8 = 2\times (64 - 1 \times 40) - 1\times 40$
$8 = 2\times 64 - 3\times 40$
For the first equation in the list, we get $40 = 168 - 2 \times 64$
$8 = 2\times 64 - 3 \times (168 - 2 \times 64)$
$8 = -3 \times 168 + 8 \times 64$
$\therefore x = -3, y = 8$

## Proof

Recall that

$a = k_0b + r_1, \quad 0 < r_1 < b$
$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$
$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$
$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$
... ...
$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad \quad 0 < r_{n -1} < r_n$
$r_{n -1} = k_nr_n, \quad\quad\quad\quad \quad r_n = 0$

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

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

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

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

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

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

Substitute Eq. 5 into Eq. 4:

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

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

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

# Efficiency

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

## Number of Steps - Lamé's Theorem

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

Proof

Recall the division equations from the Euclidean algorithm,

$a = k_0b + r_1, \quad 0 < r_1 < b$
$b = k_1r_1 + r_2 , \quad 0 < r_2 < r_1$
$r_1 = k_2r_2 + r_3, \quad 0 < r_3 < r_2$
$r_2 = k_3r_3 + r_4, \quad 0 < r_4 < r_3$
... ...
$r_{n -2} = k_{n - 1}r_{n -1} + r_n,\quad 0 < r_n < r_{n -1}$
$r_{n -1} = k_nr_n, \quad r_{n+1} = 0$

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

Notations:

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

Analyze the division equations and we will have three conclusions:

• $r_n$ couldn't be 0, as otherwise all the remainders would be 0. Hence, $r_n \geqslant 1 = F_2$.
• We know that $r_{n- 1} > r_n$. Thus, according to the last equation $r_{n -1} = k_nr_n$, $k_n$ should be greater than 1: $k_n \geqslant 2$. Therefore, $r_{n -1} = k_nr_n \geqslant 2 r_n \geqslant 2F_2 = 2 = F_3$.
• $k_{n -1}$ is an integer, so $k_{n -1} \geqslant 1$. Thus, $r_{n -2} \geqslant r_n + r_{n -1}$. Since $r_{n -1} \geqslant F_3$ and $r_{n} \geqslant F_2,$ we have $r_{n-2} \geqslant F_2 + F_3 = F_4$.

Simplify the three conclusions:

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

According to induction,

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

...

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

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

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

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

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

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

$k > \log_{10} b > \frac{n}{5}$
$k > \frac{n}{5}$
$5k > n$
$5k +1 > n + 1$
$5k \geqslant n + 1$
$n + 1 \leqslant 5k$.

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

## Shortcomings of the Euclidean Algorithm

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

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

Stein's algorithm has the following conclusions:

• $gcd(m, 0) = m, gcd(0, m) = m.$It is because every number except 0 divides 0 and m is the biggest number that can divide itself.
• If e and f are both even integers, then $gcd(e, f) = 2 \cdot gcd\left ( \frac{e}{2}, \frac{f}{2} \right )$, because 2 is definitely a common divisor of two even integers.
• If e is even and f is odd, then $gcd(e, f) = gcd \left ( \frac{e}{2}, f \right )$, because 2 is definitely not a common divisor of an even integer and an odd integer.
• Otherwise both are odd and $gcd(e, f) = gcd\left ( \frac{|e-f|}{2}, \mbox{the smaller one of e and f} \right )$. According to Euclidean algorithm, the difference of e and f, which is $|e-f|$, could also divide $gcd(e, f)$. And $\frac{|e-f|}{2}$ is an integer because the difference of two odd integers is even. Thus, the gcd of $\frac{|e-f|}{2}$ and the smaller one of e is the gcd of e and f.

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

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

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

Inner Computation:

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

Example:

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

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

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

# Why It's Interesting

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

# Teaching Materials

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

# References

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

# Future Directions for this Page

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

Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 212, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.859497606754303, "perplexity_flag": "middle"}