УказательРазделыОбозначенияАвторО проекте


§

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


Т

Теорема [Ламе]1). Пусть 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} \ .

Обозначим число2)

\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}).

Источник. Слегка переделанное доказательство из

Uspensky J.V., Heaslet M.A. Elementary Number Theory. New York. McGraw-Hill. 1941
1) Ламé Габриель (Lamé Gabriel, 1795-1870) — французский математик и инженер.
2) Оно известно как число золотого сечения и его принято обозначать \varphi.

2018/10/17 22:26 редактировал au