Editing Euclidean algorithm (section)

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