Изменения

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел $a > b > 0$, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи $F_{N+2}$ и $F_{N+1}$ соответственно. Тогда, если алгоритм Евклида требует N шагов для пары чисел $(a,b)$, где $a > b$, выполняются следующие неравенства $a ≥ F_{N+2}$ и $b ≥ F_{N+1}$. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами $a = q0b q_0b + r0r_0$, и алгоритм Евклида для пары чисел $(b,r0r_0)$, где b > r0, требует M − 1 шагов. По предположению индукции имеем $b ≥ F_{M+1}$ и $r0 r_0 >= F_M$. Следовательно, $a = q_0b + r_0 ≥ b + r_0 ≥ F_{M+1} + F_M = F_{M+2}$, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году