Теоретико-числовые свойства чисел Фибоначчи

(a) Будем доказывать утверждение по индукции. База очевидна. Переход: согласно алгоритму Евклида, и согласно индукционному предположению.

(b) Для доказательства воспользуемся утверждением

Если его истинность доказана, то согласно алгоритму Евклида

последний переход выполнен в силу пункта

Итак, будем доказывать утверждение индукцией по База очевидна. Покажем переход. согласно индукционному предположению, откуда что и требовалось доказать.

(c) Результат пункта можно интерпретировать как алгоритм Евклида на индексах чисел Фибоначчи (стандартный алгоритм Евклида утверждает, что
). Как мы знаем, алгоритм Евклида для чисел и завершается конфигурацией поэтому если применять к паре чисел и пункт так же, как мы бы применяли алгоритм Евклида к и то в конце получится что и требовалось доказать.

(d) Воспользуемся пунктом Если то согласно откуда либо Второй вариант невозможен по условию, значит что и требовалось. Обратно аналогично: если то откуда и значит