Вспомогательная страница к пункту АЛГОРИТМ ЕВКЛИДА. Требуется знакомство с числами Фибоначчи (формулой Бине).

Теорема [Ламе]¹⁾. Пусть $ B>A>0 $. Количество делений, необходимых для вычисления $ \operatorname{HOD} (A,B) $ по алгоритму Евклида не превосходит умноженного на $ 5_{} $ количества цифр в десятичном представлении $ A_{} $.

Доказательство. Пусть алгоритм Евклида приводит к результату через $ k_{} $ делений: $$ \begin{array}{lcl} B&=&Aq_1+r_1 \ , \quad 0<r_1<A\ , \\ A&=&r_1q_2+r_2 \ , \quad 0<r_2<r_1, \\ r_1&=&r_2q_3+r_3 \ , \quad 0<r_3<r_2, \\ \dots && \dots \\ r_{j-2}&=&r_{j-1}q_{j}+r_{j} \ , \quad 0<r_{j}<r_{j-1}, \\ \dots && \dots \\ r_{k-2}&=&r_{k-1}q_{k}+r_{k} \ , \quad 0<r_{k}<r_{k-1}, \\ r_{k-1}&=&r_{k}q_{k+1} . \end{array} $$ Все частные $ q_1,q_2,\dots,q_{k} $ больше или равны $ 1_{} $, но $ q_{k+1}\ge 2 $ поскольку, по предположению, $ r_{k-1}>r_{k} $. Тогда из равенств алгоритма следуют неравенства: $$ r_{k}\ge 1,\ r_{k-1}\ge 2 r_k,\ r_{k-2}\ge r_{k-1}+r_k,\ r_{k-3}\ge r_{k-2}+r_{k-1},\dots,A>r_1+r_2 \ .$$ Рассмотрим теперь числа Фибоначчи $ \{F_n\}_{n=1}^{\infty} $, задаваемые уравнением $ F_n=F_{n-1}+F_{n-2} $ при $ n>2 $, а также условиями $ F_1=1,F_2=2 $. Из предыдущих неравенств имеем: $$ r_k\ge F_1,\ r_{k-1} \ge F_2,\ r_{k-2}\ge r_{k-1}+r_k\ge F_1+F_2=F_3, \ r_{k-3}\ge r_{k-2}+r_{k-1}\ge F_2+F_3=F_4, \dots $$ и, применяя индукцию, выводим общую оценку для остатка: $$ r_{j} \ge F_{k-j+1} \ . $$ В случае $ j=0 $ эта оценка дает неравенство: $$ F_{k+1}\le A \ , $$ из которого мы вытащим оценку для $ k_{} $ с помощью формулы Бине $$ F_{k+1} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{k+2} - \left( \frac{1-\sqrt{5}}{2} \right)^{k+2} \right] \ . $$ Докажем, что $$ \left( \frac{1+\sqrt{5}}{2} \right)^{k} < F_{k+1} \ . $$ В самом деле, $$ F_{k+1} = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^{k+2} \left[ 1 - \left( \frac{1-\sqrt{5}}{1+\sqrt{5}} \right)^{k+2} \right] \ . $$ Поскольку $$ \left| \frac{1-\sqrt{5}}{1+\sqrt{5}} \right| < 1 $$ то $$ 1 -\left( \frac{1-\sqrt{5}}{1+\sqrt{5}} \right)^{k+2} > 1 -\left( \frac{1-\sqrt{5}}{1+\sqrt{5}} \right)^{2} \left|\frac{1-\sqrt{5}}{1+\sqrt{5}} \right|^k> 1 -\left( \frac{1-\sqrt{5}}{1+\sqrt{5}} \right)^{2}=\frac{4\,\sqrt{5}}{(1+\sqrt{5})^2} $$ и $$ F_{k+1}> \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^{k+2}\frac{4\,\sqrt{5}}{(1+\sqrt{5})^2}= \frac{4}{(1+\sqrt{5})^2} \left( \frac{1+\sqrt{5}}{2} \right)^{2}\left( \frac{1+\sqrt{5}}{2} \right)^{k} =\left( \frac{1+\sqrt{5}}{2} \right)^{k} \ . $$ Обозначим число²⁾ $$ \lambda=\frac{1+\sqrt{5}}{2} \ . $$ Тогда имеем: $$ \lambda^k < F_{k+1}\le A , $$ откуда $$ k < \log_{\lambda} A = \frac{\operatorname{lg}\ A}{\operatorname{lg}\ \lambda} \ . $$ Если число $ A_{} $ состоит из $ s_{} $ цифр: $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} $, то $ A<10^s $, следовательно $$ k<s \frac{1}{\operatorname{lg}\ \lambda} \approx s\cdot 4.7849719 < 5\, s \ . $$ ♦

Доказательство теоремы подсказывает и пример «самых плохих» чисел в смысле количества делений в алгоритме Евклида.

Пример. Вычислить $ \operatorname{HOD} (987, 1597) $, т.е. чисел Фибоначчи $ F_{15} $ и $ F_{16} $.

Решение. Легко увидеть, что в алгоритме Евклида для последовательных чисел Фибоначчи все частные $ q_1,q_2,\dots,q_{k} $ будут равны $ 1_{} $, а остатки $ r_{k} $ — будут опять-таки числами Фибоначчи: $$F_{16}=F_{15}+F_{14},\ F_{15}=F_{14}+F_{13},\dots,\ F_{3}=F_2+F_1, F_2=2\,F_1 \ . $$ $ \operatorname{HOD} (987, 1597)=1=F_1 $ и появляется он при $ 14_{} $-м делении. ♦

Найти линейное представление для $ \operatorname{HOD} (F_n,F_{n+1}) $.

Источник