1.7: Теорема кульгавого

У цьому розділі наведено оцінку кількості кроків, необхідних для пошуку найбільшого спільного дільника двох цілих чисел за допомогою алгоритму Евкліда. Для цього нам доведеться ввести числа Фібоначчі заради доведення леми, яка дає оцінку зростання чисел Фібоначчі в послідовності Фібоначчі. Лема, яку ми доведемо, буде використана в доведенні теореми Ламе.

Послідовність Фібоначчі визначається рекурсивно$f_1=1$$f_2=1$, а

$$f_{n}=f_{n-1}+f_{n-2} \mbox{for} \ \ n\geq 3.$$ члени в послідовності називаються числами Фібоначчі.

У наступній лемі наведемо нижню межу зростання чисел Фібоначчі. Ми покажемо, що числа Фібоначчі ростуть швидше, ніж геометричний ряд із загальним співвідношенням$\alpha=(1+\sqrt{5})/2$.

[lem2] Для$n\geq 3$, у нас є$f_n>\alpha^{n-2}$ де$\alpha=(1+\sqrt{5})/2$.

Ми використовуємо другий принцип математичної індукції, щоб довести свій результат. Легко помітити, що це вірно для$n=3$ і$n=4$. Припустимо, що$\alpha^{k-2}<f_k$ для всіх цілих чисел$k$ де$k\leq n$. Тепер$\alpha$, оскільки є розв'язком многочлена$x^2-x-1=0$, ми маємо$\alpha^2=\alpha+1$. Звідси

$$\alpha^{n-1}=\alpha^2.\alpha^{n-3}=(\alpha+1).\alpha^{n-3}=\alpha^{n-2}+\alpha^{n-3}.$$ За індуктивною гіпотезою ми маємо $$\alpha^{n-2}<f_n, \ \ \ \alpha^{n-3}<f_{n-1}.$$ Після додавання двох нерівностей, ми отримуємо $$\alpha^{n-1}<f_{n}+f_{n-1}=f_{n+1}.$$

Зараз ми представляємо теорему Ламе.

за допомогою алгоритму Евкліда знайти найбільший спільний дільник двох натуральних чисел має кількість ділень менше або дорівнює п'ятикратному числу десяткових знаків у мінімумі з двох цілих чисел.

$a$$b$Дозволяти і бути два натуральних числа де$a>b$. Застосовуючи алгоритм Евкліда, щоб знайти найбільший спільний дільник двох цілих чисел з$a=r_0$ і$b=r_1$, ми отримуємо

$$\begin{aligned} r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\ r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\ &.& \\ &.& \\ &.& \\ r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\ r_{n-1}&=&r_{n}q_{n}.\end{aligned}$$ Зверніть увагу, що кожен з$q_1,q_2,...,q_{n-1}$ коефіцієнтів все більше 1$q_n\geq 2$ і це тому, що$r_n<r_{n-1}$. Таким чином, ми маємо $$\begin{aligned} r_n&\geq& 1=f_2,\\ r_{n-1}&\geq& 2r_n\geq 2f_2=f_3,\\ r_{n-2}&\geq& r_{n-1}+r_n\geq f_3+f_2=f_4,\\ r_{n-3}&\geq& r_{n-2}+r_{n-1}\geq f_4+f_3=f_5,\\ &.&\\ &.&\\ &.&\\ r_2&\geq& r_3+r_4\geq f_{n-1}+f_{n-2}=f_n,\\ b&=& r_1\geq r_2+r_3\geq f_n+f_{n-1}=f_{n+1}.\end{aligned}$$ Таким чином помітити, що$b\geq f_{n+1}$. За Леммою [лем2], ми маємо$f_{n+1}>\alpha^{n-1}$ для$n>2$. В результаті ми маємо$b>\alpha^{n-1}$. Тепер зверніть увагу, так як $$\log_{10}\alpha>\frac{1}{5},$$ ми бачимо, що $$log_{10}b>(n-1)/5.$$ Таким чином, ми $$n-1<5log_{10}b.$$ тепер нехай$b$ має$k$ десяткові цифри. В результаті ми маємо$b<10^k$ і таким чином$log_{10}b<k$. Звідси ми робимо висновок, що$n-1<5k$. Оскільки$k$ є цілим числом, ми робимо висновок, що$n\leq 5k$.

Вправи

1. Знайдіть верхню межу кількості кроків у евклідовому алгоритмі, який використовується для пошуку найбільшого спільного дільника 38472 та 957748838.
2. Знайдіть верхню межу кількості кроків у евклідовому алгоритмі, який використовується для пошуку найбільшого спільного дільника 15 та 75. Перевірте результат за допомогою алгоритму Евкліда, щоб знайти найбільший спільний дільник двох цілих чисел.

Дописувачі та атрибуція

• Template:ContribRaji