Изменения

==Наихудший случай алгоритма Евклида==

Если для алгоритма Евклида требуются 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 + r0, и алгоритм Евклида для пары чисел (b,r0), где b > r0, требует M − 1 шагов. По предположению индукции имеем $b ≥ F_{M+1}$ и $r0 >= F_M$. Следовательно, $a = q_0b + r_0 ≥ b + r_0 ≥ F_{M+1} + F_M = F_{M+2}$, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году