Editing Euclidean algorithm (section)

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