1.7: Теорема кульгавого
У цьому розділі наведено оцінку кількості кроків, необхідних для пошуку найбільшого спільного дільника двох цілих чисел за допомогою алгоритму Евкліда. Для цього нам доведеться ввести числа Фібоначчі заради доведення леми, яка дає оцінку зростання чисел Фібоначчі в послідовності Фібоначчі. Лема, яку ми доведемо, буде використана в доведенні теореми Ламе.
Послідовність Фібоначчі визначається рекурсивноf1=1f2=1, аfn=fn−1+fn−2for n≥3. члени в послідовності називаються числами Фібоначчі.
У наступній лемі наведемо нижню межу зростання чисел Фібоначчі. Ми покажемо, що числа Фібоначчі ростуть швидше, ніж геометричний ряд із загальним співвідношеннямα=(1+√5)/2.
[lem2] Дляn≥3, у нас єfn>αn−2 деα=(1+√5)/2.
Ми використовуємо другий принцип математичної індукції, щоб довести свій результат. Легко помітити, що це вірно дляn=3 іn=4. Припустимо, щоαk−2<fk для всіх цілих чиселk деk≤n. Теперα, оскільки є розв'язком многочленаx2−x−1=0, ми маємоα2=α+1. Звідсиαn−1=α2.αn−3=(α+1).αn−3=αn−2+αn−3. За індуктивною гіпотезою ми маємоαn−2<fn, αn−3<fn−1. Після додавання двох нерівностей, ми отримуємоαn−1<fn+fn−1=fn+1.
Зараз ми представляємо теорему Ламе.
за допомогою алгоритму Евкліда знайти найбільший спільний дільник двох натуральних чисел має кількість ділень менше або дорівнює п'ятикратному числу десяткових знаків у мінімумі з двох цілих чисел.
abДозволяти і бути два натуральних числа деa>b. Застосовуючи алгоритм Евкліда, щоб знайти найбільший спільний дільник двох цілих чисел зa=r0 іb=r1, ми отримуємоr0=r1q1+r2 0≤r2<r1,r1=r2q2+r3 0≤r3<r2,...rn−2=rn−1qn−1+rn 0≤rn<rn−1,rn−1=rnqn. Зверніть увагу, що кожен зq1,q2,...,qn−1 коефіцієнтів все більше 1qn≥2 і це тому, щоrn<rn−1. Таким чином, ми маємоrn≥1=f2,rn−1≥2rn≥2f2=f3,rn−2≥rn−1+rn≥f3+f2=f4,rn−3≥rn−2+rn−1≥f4+f3=f5,...r2≥r3+r4≥fn−1+fn−2=fn,b=r1≥r2+r3≥fn+fn−1=fn+1. Таким чином помітити, щоb≥fn+1. За Леммою [лем2], ми маємоfn+1>αn−1 дляn>2. В результаті ми маємоb>αn−1. Тепер зверніть увагу, так якlog10α>15, ми бачимо, щоlog10b>(n−1)/5. Таким чином, миn−1<5log10b. тепер нехайb маєk десяткові цифри. В результаті ми маємоb<10k і таким чиномlog10b<k. Звідси ми робимо висновок, щоn−1<5k. Оскількиk є цілим числом, ми робимо висновок, щоn≤5k.
Вправи
- Знайдіть верхню межу кількості кроків у евклідовому алгоритмі, який використовується для пошуку найбільшого спільного дільника 38472 та 957748838.
- Знайдіть верхню межу кількості кроків у евклідовому алгоритмі, який використовується для пошуку найбільшого спільного дільника 15 та 75. Перевірте результат за допомогою алгоритму Евкліда, щоб знайти найбільший спільний дільник двох цілих чисел.