Пункт 10. Континуанти. Аналіз алгоритму Евкліда.

Згадаємо рекурентні співвідношення для чисельників і знаменників прямуючих дробів:

P _s = q _s P _{s -1} + P _{s -2} - чисельники

Q _s = q _s Q _{s -1} + Q _{s -2} - знаменники.

Початкові умови: P ₁ = q ₁ , P ₀ = 1, Q ₁ = 1, Q ₀ = 0.

Тепер, коли ці співвідношення коштують як живі в нас перед очима в зручному місці, давайте розглянемо не їхній, а трехдиагональный визначник:

 =(q₁,q₂,…,q_n)

Визначення. Визначник (детермінант), позначений декількома рядками вище через ( q₁ q₂ ... q _n ), називається континуантою n -ого порядку. Числа q ₁ , q ₂ ,..., q _n надалі будуть у нас неповними частками з алгоритму Евкліда, тому є цілими.

Розкладемо континуанту n-ого порядку по останньому стовпцю. Одержимо:

( q ₁ q ₂ ... q _n ) = q _n ( q ₁ q ₂ ... q _{n -1} ) + ( q ₁ q ₂ ... q _{n -2} ).

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

Лема 1. Континуанта ( q₁ q₂ ... q_n ) дорівнює сумі всіляких добутків елементів q₁ , q₂ , ..., q_n одне з яких містить усі ці елементи, а інші виходять з нього викиданням однієї чи декількох пар співмножників із сусідніми номерами (Якщо викинули всі співмножники, то вважаємо, що залишилася 1).

 Приклад, що пояснює.

( q₁ q₂ q₃ q₄ q₅ q₆ ) = q₁ q₂ q₃ q₄ q₅ q₆ + q₃ q₄ q₅ q₆ + q₁ q₄ q₅ q₆ + q₁ q₂ q₅ q₆ + q₁ q₂ q₃ q₆ + q₁ q₂ q₃ q₄ + q₅ q₆ + q₃ q₆ + q₁ q₆ + q₃ q₄ + q₁ q₄ + q₁ q₂ + 1.

Доказ. База індукції:

( q ₁ ) = q ₁ , ( q ₁ q ₂ ) == q ₁ q ₂ + 1,

і твердження леми справедливе для континуант першого і другого порядків.

Крок індукції. Нехай твердження леми вірне для континуант (n-2)-го і (n-1)-ого порядків. Тоді маємо:  ( q₁ q₂ ... q_n ) = q_n ( q₁ q₂ ... q_{n -1} ) + ( q₁ q₂ ... q_{n -2} )

і розглядування цієї рівності в поєднанні з уявним прикидуванням, які добутки вийдуть від множення континуанти ( q₁ q₂ ... q_{n -1} ) на q_n , доводить необхідне.

Спостереження. Кількість доданків в континуанті n -ого порядку є сумою числа доданків у континуантах (n-1)-ого і (n-2)-го порядків, тобто континуанта ( q₁ q₂ ... q_n ) містить F_{n +1} складову, де F _{n +1} - ( n +1)-ше число Фібоначчі.

Лема 2.

Доказ. База індукції:

Крок індукції. Нехай вірно, що

Тоді:

Твердження леми 2, що встановлює прямий зв'язок континуант із ланцюговими дробами, уперше помітив Леонард Эйлер.