Editing Euclidean algorithm (section)

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