Editing Euclidean algorithm (section)

=== 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}}.