Editing Euclidean algorithm (section)

== Background: greatest common divisor ==
{{main|Greatest common divisor}}

The Euclidean algorithm calculates the greatest common divisor (GCD) of two [[natural number]]s {{mvar|a}} and {{mvar|b}}. The greatest common divisor {{mvar|g}} is the largest natural number that divides both {{mvar|a}} and {{mvar|b}} without leaving a remainder. Synonyms for GCD include ''greatest common factor'' (GCF), ''highest common factor'' (HCF), ''highest common divisor'' (HCD), and ''greatest common measure'' (GCM). The greatest common divisor is often written as {{math|gcd(''a'', ''b'')}} or, more simply, as {{math|(''a'', ''b'')}},<ref>{{Harvnb|Stark|1978|p=16}}</ref> although the latter notation is ambiguous, also used for concepts such as an [[Ideal (ring theory)|ideal]] in the [[ring of integers]], which is closely related to GCD.

If {{math|gcd(''a'', ''b'') {{=}} 1}}, then {{mvar|a}} and {{mvar|b}} are said to be [[Coprime integers|coprime]] (or relatively prime).<ref>{{Harvnb|Stark|1978|p=21}}</ref> This property does not imply that {{mvar|a}} or {{mvar|b}} are themselves [[prime number]]s.<ref>{{Harvnb|LeVeque|1996|p=32}}</ref> For example, {{math|6}} and {{math|35}} factor as {{math|1=6 = 2 × 3}} and {{math|1=35 = 5 × 7}}, so they are not prime, but their prime factors are different, so {{math|6}} and {{math|35}} are coprime, with no common factors other than&nbsp;{{math|1}}.

[[File:24x60.svg|thumb|upright|alt="Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."|A 24×60 rectangle is covered with ten 12×12 square tiles, where 12 is the GCD of 24 and 60. More generally, an {{math|''a''×''b''}} rectangle can be covered with square tiles of side-length {{mvar|c}} only if {{mvar|c}} is a common divisor of {{math|''a''}} and {{math|''b''}}.]]

Let {{math|''g'' {{=}} gcd(''a'', ''b'')}}. Since {{mvar|a}} and {{mvar|b}} are both multiples of {{mvar|g}}, they can be written {{math|''a'' {{=}} ''mg''}} and {{mvar|''b'' {{=}} ''ng''}}, and there is no larger number {{math|''G'' > ''g''}} for which this is true. The natural numbers {{mvar|m}} and {{mvar|n}} must be coprime, since any common factor could be factored out of {{mvar|m}} and {{mvar|n}} to make {{mvar|g}} greater. Thus, any other number {{mvar|c}} that divides both {{mvar|a}} and {{mvar|b}} must also divide {{mvar|g}}. The greatest common divisor {{mvar|g}} of {{mvar|a}} and {{mvar|b}} is the unique (positive) common divisor of {{mvar|a}} and {{mvar|b}} that is divisible by any other common divisor {{mvar|c}}.<ref>{{Harvnb|LeVeque|1996|p=31}}</ref>

The greatest common divisor can be visualized as follows.<ref>{{cite book | last = Grossman|first= J. W. | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref> Consider a rectangular area {{mvar|a}} by {{mvar|b}}, and any common divisor {{mvar|c}} that divides both {{mvar|a}} and {{mvar|b}} exactly. The sides of the rectangle can be divided into segments of length {{mvar|c}}, which divides the rectangle into a grid of squares of side length {{mvar|c}}. The GCD {{mvar|g}} is the largest value of {{mvar|c}} for which this is possible. For illustration, a {{math|24×60}} rectangular area can be divided into a grid of: {{math|1×1}} squares, {{math|2×2}} squares, {{math|3×3}} squares, {{math|4×4}} squares, {{math|6×6}} squares or {{math|12×12}} squares. Therefore, {{math|12}} is the GCD of {{math|24}} and {{math|60}}. A {{math|24×60}} rectangular area can be divided into a grid of {{math|12×12}} squares, with two squares along one edge ({{math|24/12 {{=}} 2}}) and five squares along the other ({{math|60/12 {{=}} 5}}).

The greatest common divisor of two numbers {{mvar|a}} and {{mvar|b}} is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both {{mvar|a}} and {{mvar|b}}.<ref name="Schroeder_21" >{{Harvnb|Schroeder|2005|pp=21–22}}</ref> For example, since {{math|1386}} can be factored into {{math|2 × 3 × 3 × 7 × 11}}, and {{math|3213}} can be factored into {{math|3 × 3 × 3 × 7 × 17}}, the GCD of {{math|1386}} and {{math|3213}} equals {{math|63 {{=}} 3 × 3 × 7}}, the product of their shared prime factors (with 3 repeated since {{math|3 × 3}} divides both). If two numbers have no common prime factors, their GCD is {{math|1}} (obtained here as an instance of the [[empty product]]); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.<ref>{{Harvnb|Schroeder|2005|p=19}}</ref><ref>{{cite book | last1 = Ogilvy | first1 = C. S. | author1-link = C. Stanley Ogilvy | last2 = Anderson | first2 = J. T. | year = 1966 | title = Excursions in number theory | publisher = [[Oxford University Press]] | location = New York | pages = 27–29}}</ref> [[integer factorization|Factorization]] of large integers is believed to be a computationally very difficult problem, and the security of many widely used [[cryptographic protocol]]s is based upon its infeasibility.<ref name="Schroeder_216" >{{Harvnb|Schroeder|2005|pp=216–219}}</ref>

Another definition of the GCD is helpful in advanced mathematics, particularly [[ring theory]].<ref name="Leveque_p33" /> The greatest common divisor {{mvar|g}} of two nonzero numbers {{mvar|a}} and {{mvar|b}} is also their smallest positive integral linear combination, that is, the smallest positive number of the form {{math|''ua'' + ''vb''}} where {{mvar|u}} and {{mvar|v}} are integers. The set of all integral linear combinations of {{mvar|a}} and {{mvar|b}} is actually the same as the set of all multiples of {{mvar|g}} ({{mvar|mg}}, where {{mvar|m}} is an integer). In modern mathematical language, the [[ideal (ring theory)|ideal]] generated by {{mvar|a}} and {{mvar|b}} is the ideal generated by&nbsp;{{mvar|g}} alone (an ideal generated by a single element is called a [[principal ideal]], and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of {{mvar|a}} and {{mvar|b}} also divides the GCD (it divides both terms of {{math|''ua''&nbsp;+&nbsp;''vb''}}). The equivalence of this GCD definition with the other definitions is described below.

The GCD of three or more numbers equals the product of the prime factors common to all the numbers,<ref>{{Harvnb|Stark|1978|p=25}}</ref> but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.<ref>{{Harvnb|Ore|1948|pp=47–48}}</ref> For example,
: {{math|1=gcd(''a'', ''b'', ''c'') = gcd(''a'', gcd(''b'', ''c'')) = gcd(gcd(''a'', ''b''), ''c'') = gcd(gcd(''a'', ''c''), ''b'').}}

Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.

=== Procedure ===
{{Euclidean algorithm steps}}
The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math>r_{-2} = a</math> and <math>r_{-1} = b</math> and will eventually terminate with the integer zero: <math>\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}</math> with <math>r_{k+1} < r_k</math>. The integer <math>r_{n-1}</math> will then be the GCD and we can state <math>\text{gcd}(a,b) = r_{n-1}</math>. The algorithm indicates how to construct the intermediate remainders <math>r_k</math> via [[Euclidean division|division-with-remainder]] on the preceding pair <math>(r_{k-2},\ r_{k-1})</math> by finding an integer quotient <math>q_k</math> so that:
: <math>r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0.</math>

Because the sequence of non-negative integers <math>\{ r_k \}</math> is strictly decreasing, it eventually [[Well-ordering principle|must terminate]]. In other words, since <math>r_k \ge 0</math> for every <math>k</math>, and each <math>r_k</math> is an integer that is strictly smaller than the preceding <math>r_{k-1}</math>, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the {{math|''n''}}th step with <math>r_n</math> equal to zero.<ref>{{Harvnb|Stark|1978|p=18}}</ref>

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math>\{r_{-2} = 1071,\ r_{-1} = 462 \}</math> and in order to find <math>r_0</math>, we need to find integers <math>q_0</math> and <math>r_0 < r_{-1}</math> such that:
: <math>1071 = q_0 \cdot 462 + r_0</math>.

This is the quotient <math>q_0 = 2</math> since <math>1071 = 2 \cdot 462 + 147</math>. This determines <math>r_0 = 147</math> and so the sequence is now <math>\{1071,\ 462,\ r_0 = 147 \}</math>. The next step is to continue the sequence to find <math>r_1</math> by finding integers <math>q_1</math> and <math>r_1 < r_0</math> such that:
: <math>462 = q_1 \cdot 147 + r_1</math>.

This is the quotient <math>q_1 = 3</math> since <math>462 = 3 \cdot 147 + 21</math>. This determines <math>r_1 = 21</math> and so the sequence is now <math>\{1071,\ 462,\ 147,\ r_1 = 21 \}</math>. The next step is to continue the sequence to find <math>r_2</math> by finding integers <math>q_2</math> and <math>r_2 < r_1</math> such that:
: <math>147 = q_2 \cdot 21 + r_2</math>.

This is the quotient <math>q_2 = 7</math> since <math>147 = 7 \cdot 21 + 0</math>. This determines <math>r_2 = 0</math> and so the sequence is completed as <math>\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}</math> as no further non-negative integer smaller than <math>0</math> can be found. The penultimate remainder <math>21</math> is therefore the requested GCD:
: <math>\text{gcd}(1071,\ 462) = 21.</math>

We can generalize slightly by dropping any ordering requirement on the initial two values <math>a</math> and <math>b</math>. If <math>a = b</math>, the algorithm may continue and trivially find that <math>\text{gcd}(a,\ a) = a</math> as the sequence of remainders will be <math>\{a,\ a,\ 0\}</math>. If <math>a < b</math>, then we can also continue since <math>a \equiv 0 \cdot b + a</math>, suggesting the next remainder should be <math>a</math> itself, and the sequence is <math>\{a,\ b,\ a,\ \cdots \}</math>. Normally, this would be invalid because it breaks the requirement <math>r_0 < r_{-1}</math> but now we have <math>a < b</math> by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy <math>r_0 < b</math> and everything continues as above. The only modifications that need to be made are that <math>r_{k} < r_{k-1}</math> only for <math>k \ge 0</math>, and that the sub-sequence of non-negative integers <math>\{ r_{k-1} \}</math> for <math>k \ge 0</math> is strictly decreasing, therefore excluding <math>a = r_{-2}</math> from both statements.

=== Proof of validity ===
The validity of the Euclidean algorithm can be proven by a two-step argument.<ref>{{Harvnb|Stark|1978|pp=16–20}}</ref> In the first step, the final nonzero remainder {{math|''r''<sub>''N''−1</sub>}} is shown to divide both {{math|''a''}} and&nbsp;{{math|''b''}}. Since it is a common divisor, it must be less than or equal to the greatest common divisor&nbsp;{{math|''g''}}. In the second step, it is shown that any common divisor of {{math|''a''}} and {{math|''b''}}, including&nbsp;{{math|''g''}}, must divide {{math|''r''<sub>''N''−1</sub>}}; therefore, {{math|''g''}} must be less than or equal to {{math|''r''<sub>''N''−1</sub>}}. These two opposite inequalities imply {{math|1=''r''<sub>''N''−1</sub> = ''g''}}.

To demonstrate that {{math|''r''<sub>''N''−1</sub>}} divides both {{math|''a''}} and {{math|''b''}} (the first step), {{math|''r''<sub>''N''−1</sub>}} divides its predecessor {{math|''r''<sub>''N''−2</sub>}}
: {{math|1=''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub>}}
since the final remainder {{math|''r''<sub>''N''</sub>}} is zero. {{math|''r''<sub>''N''−1</sub>}} also divides its next predecessor {{math|''r''<sub>''N''−3</sub>}}
: {{math|1=''r''<sub>''N''−3</sub> = ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub> + ''r''<sub>''N''−1</sub>}}
because it divides both terms on the right-hand side of the equation. Iterating the same argument, {{math|''r''<sub>''N''−1</sub>}} divides all the preceding remainders, including {{math|''a''}} and {{math|''b''}}. None of the preceding remainders {{math|''r''<sub>''N''−2</sub>}}, {{math|''r''<sub>''N''−3</sub>}}, etc. divide {{math|''a''}} and {{math|''b''}}, since they leave a remainder. Since {{math|''r''<sub>''N''−1</sub>}} is a common divisor of {{math|''a''}} and&nbsp;{{math|''b''}}, {{math|''r''<sub>''N''−1</sub> ≤ ''g''}}.

In the second step, any natural number {{math|''c''}} that divides both {{math|''a''}} and {{math|''b''}} (in other words, any common divisor of {{math|''a''}} and {{math|''b''}}) divides the remainders {{math|''r''<sub>''k''</sub>}}. By definition, {{math|''a''}} and {{math|''b''}} can be written as multiples of {{math|''c''}}: {{math|1=''a'' = ''mc''}} and {{math|1=''b'' = ''nc''}}, where {{math|''m''}} and {{math|''n''}} are natural numbers. Therefore, {{math|''c''}} divides the initial remainder {{math|''r''<sub>0</sub>}}, since {{math|1=''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub>''b'' = ''mc'' − ''q''<sub>0</sub>''nc'' = (''m'' − ''q''<sub>0</sub>''n'')''c''}}. An analogous argument shows that {{math|''c''}} also divides the subsequent remainders {{math|''r''<sub>1</sub>}}, {{math|''r''<sub>2</sub>}}, etc. Therefore, the greatest common divisor {{math|''g''}} must divide {{math|''r''<sub>''N''−1</sub>}}, which implies that {{math|''g'' ≤ ''r''<sub>''N''−1</sub>}}. Since the first part of the argument showed the reverse ({{math|''r''<sub>''N''−1</sub> ≤ ''g''}}), it follows that {{math|1=''g'' = ''r''<sub>''N''−1</sub>}}. Thus, {{math|''g''}} is the greatest common divisor of all the succeeding pairs:<ref>{{harvnb|Knuth|1997|p=320}}</ref><ref name="Lovasz_2003">{{cite book | last1 = Lovász |first1=L.|author1-link=László Lovász|last2= Pelikán|first2=J.|last3=Vesztergombi|first3= K. |author3-link= Katalin Vesztergombi | year = 2003 | title = Discrete Mathematics: Elementary and Beyond | publisher = Springer-Verlag | location = New York | isbn = 0-387-95584-4 | pages = 100–101}}</ref>
: {{math|1=''g'' = gcd(''a'', ''b'') = gcd(''b'', ''r''<sub>0</sub>) = gcd(''r''<sub>0</sub>, ''r''<sub>1</sub>) = ... = gcd(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''r''<sub>''N''−1</sub>}}.

=== Worked example ===
[[File:Euclidean algorithm 1071 462.gif|upright|thumb|alt=Animation in which progressively smaller square tiles are added to cover a rectangle completely.|Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions {{math|1=''a'' = 1071}} and {{math|1=''b'' = 462}}. Squares of size {{math|462×462}} are placed within it leaving a {{math|462×147}} rectangle. This rectangle is tiled with {{math|147×147}} squares until a {{math|21×147}} rectangle is left, which in turn is tiled with {{math|21×21}} squares, leaving no uncovered area. The smallest square size, {{math|21}}, is the GCD of {{math|1071}} and {{math|462}}.]]

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of {{math|1=''a'' = 1071}} and {{math|1=''b'' = 462}}. To begin, multiples of {{math|462}} are subtracted from {{math|1071}} until the remainder is less than {{math|462}}. Two such multiples can be subtracted ({{math|1=''q''<sub>0</sub> = 2}}), leaving a remainder of {{math|147}}:
: {{math|1=1071 = 2 × 462 + 147}}.

Then multiples of {{math|147}} are subtracted from {{math|462}} until the remainder is less than {{math|147}}. Three multiples can be subtracted ({{math|1=''q''<sub>1</sub> = 3}}), leaving a remainder of {{math|21}}:
: {{math|1=462 = 3 × 147 + 21}}.

Then multiples of {{math|21}} are subtracted from {{math|147}} until the remainder is less than {{math|21}}. Seven multiples can be subtracted ({{math|1=''q''<sub>2</sub> = 7}}), leaving no remainder:
: {{math|1=147 = 7 × 21 + 0}}.

Since the last remainder is zero, the algorithm ends with {{math|21}} as the greatest common divisor of {{math|1071}} and {{math|462}}. This agrees with the {{math|gcd(1071, 462)}} found by prime factorization [[#Background: greatest common divisor|above]]. In tabular form, the steps are:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
|-
!Step ''k''!!Equation!!Quotient and remainder
|-
| 0 || {{math|1=1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub>}} || {{math|1=''q''<sub>0</sub> = 2}} and {{math|1=''r''<sub>0</sub> = 147}}
|-
| 1 || {{math|1=462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub>}} || {{math|1=''q''<sub>1</sub> = 3}} and {{math|1=''r''<sub>1</sub> = 21}}
|-
| 2 || {{math|1=147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub>}} || {{math|1=''q''<sub>2</sub> = 7}} and {{math|1=''r''<sub>2</sub> = 0}}; algorithm ends
|}

=== Visualization ===
The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.<ref name="Kimberling_1983">{{cite journal | last = Kimberling|first= C.|author-link=Clark Kimberling | year = 1983 | title = A Visual Euclidean Algorithm | journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref> Assume that we wish to cover an {{math|''a''×''b''}} rectangle with square tiles exactly, where {{math|''a''}} is the larger of the two numbers. We first attempt to tile the rectangle using {{math|''b''×''b''}} square tiles; however, this leaves an {{math|''r''<sub>0</sub>×''b''}} residual rectangle untiled, where {{math|''r''<sub>0</sub> < ''b''}}. We then attempt to tile the residual rectangle with {{math|''r''<sub>0</sub>×''r''<sub>0</sub>}} square tiles. This leaves a second residual rectangle {{math|''r''<sub>1</sub>×''r''<sub>0</sub>}}, which we attempt to tile using {{math|''r''<sub>1</sub>×''r''<sub>1</sub>}} square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is {{math|21×21}} (shown in red), and {{math|21}} is the GCD of {{math|1071}} and {{math|462}}, the dimensions of the original rectangle (shown in green).

=== Euclidean division ===
{{Main|Euclidean division}}

At every step {{math|''k''}}, the Euclidean algorithm computes a quotient {{math|''q''<sub>''k''</sub>}} and remainder {{math|''r''<sub>''k''</sub>}} from two numbers {{math|''r''<sub>''k''−1</sub>}} and {{math|''r''<sub>''k''−2</sub>}}
: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}},
where the {{math|''r''<sub>''k''</sub>}} is non-negative and is strictly less than the [[absolute value]] of {{math|''r''<sub>''k''−1</sub>}}. The theorem which underlies the definition of the [[Euclidean division]] ensures that such a quotient and remainder always exist and are unique.<ref>{{cite book|title=Abstract Algebra|last1=Dummit|first1=David S.|last2=Foote|first2=Richard M.|publisher=John Wiley & Sons, Inc.|year=2004|isbn=978-0-471-43334-7|pages=270–271}}</ref>

In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, {{math|''r''<sub>''k''−1</sub>}} is subtracted from {{math|''r''<sub>''k''−2</sub>}} repeatedly until the remainder {{math|''r''<sub>''k''</sub>}} is smaller than {{math|''r''<sub>''k''−1</sub>}}. After that {{math|''r''<sub>''k''</sub>}} and {{math|''r''<sub>''k''−1</sub>}} are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the [[modulo operation]], which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply
: {{math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>}}.

=== Implementations ===
Implementations of the algorithm may be expressed in [[pseudocode]]. For example, the division-based version may be [[computer programming|programmed]] as<ref>{{harvnb|Knuth|1997|pp=319–320}}</ref>

 '''function''' gcd(a, b)
     '''while''' b ≠ 0
         t := b
         b := a '''mod''' b
         a := t
     '''return''' a

At the beginning of the {{math|''k''}}th iteration, the variable {{math|''b''}} holds the latest remainder {{math|''r''<sub>''k''−1</sub>}}, whereas the variable {{math|''a''}} holds its predecessor, {{math|''r''<sub>''k''−2</sub>}}. The step {{math|1=''b'' := ''a'' mod ''b''}} is equivalent to the above recursion formula {{math|''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>}}. The [[temporary variable]] {{math|''t''}} holds the value of {{math|''r''<sub>''k''−1</sub>}} while the next remainder {{math|''r''<sub>''k''</sub>}} is being calculated. At the end of the loop iteration, the variable {{math|''b''}} holds the remainder {{math|''r''<sub>''k''</sub>}}, whereas the variable {{math|''a''}} holds its predecessor, {{math|''r''<sub>''k''−1</sub>}}.

(If negative inputs are allowed, or if the <code>'''mod'''</code> function may return negative values, the last line must be replaced with {{nowrap|<code>'''return abs'''(a)</code>}}.)

In the subtraction-based version, which was Euclid's original version, the remainder calculation ({{nowrap|1=<code>b := a '''mod''' b</code>}}) is replaced by repeated subtraction.<ref>{{harvnb|Knuth|1997|pp=318–319}}</ref> Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when {{math|1=''a'' = ''b''}}:

 '''function''' gcd(a, b)
     '''while''' a ≠ b 
         '''if''' a > b
             a := a − b
         '''else'''
             b := b − a
     '''return''' a

The variables {{math|''a''}} and {{math|''b''}} alternate holding the previous remainders {{math|''r''<sub>''k''−1</sub>}} and {{math|''r''<sub>''k''−2</sub>}}. Assume that {{math|''a''}} is larger than {{math|''b''}} at the beginning of an iteration; then {{math|''a''}} equals {{math|''r''<sub>''k''−2</sub>}}, since {{math|''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>}}. During the loop iteration, {{math|''a''}} is reduced by multiples of the previous remainder {{math|''b''}} until {{math|''a''}} is smaller than {{math|''b''}}. Then {{math|''a''}} is the next remainder {{math|''r''<sub>''k''</sub>}}. Then {{math|''b''}} is reduced by multiples of {{math|''a''}} until it is again smaller than {{math|''a''}}, giving the next remainder {{math|''r''<sub>''k''+1</sub>}}, and so on.

The recursive version<ref>{{Harvnb|Stillwell|1997|p=14}}</ref> is based on the equality of the GCDs of successive remainders and the stopping condition {{math|1=gcd(''r''<sub>''N''−1</sub>, 0) = ''r''<sub>''N''−1</sub>}}.

 '''function''' gcd(a, b)
     '''if''' b = 0
         '''return''' a
     '''else'''
         '''return''' gcd(b, a '''mod''' b)

(As above, if negative inputs are allowed, or if the <code>'''mod'''</code> function may return negative values, the instruction {{nowrap|<code>'''return''' a</code>}} must be replaced by {{nowrap|<code>'''return max'''(a, −a)</code>}}.)

For illustration, the {{math|gcd(1071, 462)}} is calculated from the equivalent {{math|1=gcd(462, 1071 mod 462) = gcd(462, 147)}}. The latter GCD is calculated from the {{math|1=gcd(147, 462 mod 147) = gcd(147, 21)}}, which in turn is calculated from the {{math|1=gcd(21, 147 mod 21) = gcd(21, 0) = 21}}.

=== Method of least absolute remainders ===
In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder.<ref name="Ore_least_abs_remainders" >{{Harvnb|Ore|1948|p=43}}</ref><ref name="Stewart_1964">{{cite book | last = Stewart|first= B. M. | year = 1964 | title = Theory of Numbers | edition = 2nd | publisher = Macmillan | location = New York | pages = 43–44 | lccn = 64010964}}</ref> Previously, the equation
: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}}
assumed that {{math|1={{abs|''r''<sub>''k''−1</sub>}} > ''r''<sub>''k''</sub> > 0}}. However, an alternative negative remainder {{math|1=''e''<sub>''k''</sub>}} can be computed:
: {{math|1=''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>}}
if {{math|1=''r''<sub>''k''−1</sub>&nbsp;>&nbsp;0}} or
: {{math|1=''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> – 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>}}
if {{math|1=''r''<sub>''k''−1</sub>&nbsp;<&nbsp;0}}.

If {{math|1=''r''<sub>''k''</sub>}} is replaced by {{math|1=''e''<sub>''k''</sub>}}. when {{math|1={{abs|''e''<sub>''k''</sub>}} < {{abs|''r''<sub>''k''</sub>}}}}, then one gets a variant of Euclidean algorithm such that
: {{math|1={{abs|''r''<sub>''k''</sub>}} ≤ {{abs|''r''<sub>''k''−1</sub>}} / 2}}
at each step.

[[Leopold Kronecker]] has shown that this version requires the fewest steps of any version of Euclid's algorithm.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" /> More generally, it has been proven that, for every input numbers ''a'' and ''b'', the number of steps is minimal if and only if {{math|''q''<sub>''k''</sub>}} is chosen in order that <math>\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0.618,</math> where <math>\varphi</math> is the [[golden ratio]].<ref>{{cite journal|last=Lazard|first=D.|year=1977|title=Le meilleur algorithme d'Euclide pour ''K''[''X''] et '''Z''' |language=fr |journal=Comptes Rendus de l'Académie des Sciences|volume=284|pages=1–4}}</ref>