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

Рассмотрим последовательность чисел построенную рекурсивно: для всех Про такую последовательность известно, что:

(a)  для всех Это утверждение можно доказать индукцией по Действительно, так как Если утверждение уже доказано для то для оно следует из пункта задачи

(b) каждый элемент этой последовательности, кроме нулевого, это число Фибоначчи, которое делится на собственный индекс. Действительно, если для некоторого то по построению и, по доказанному,

(c) для любого элемент содержит хотя бы на один простой делитель больше, чем Поскольку то содержит все простые делители и для доказательства утверждения достаточно установить существование простого такого что но

Тот факт, что такое простое существует для всех мы тоже будем доказывать по индукции по Покажем базу для по пункту задачи 8. При этом, Переход: пусть утверждение получено для и пусть  – такое простое, что , но Тогда, по всему тому же пункту Согласно пункту Таким образом, если то так как делится на все простые делители а  – ни на какие, утверждение задачи получено. И поскольку все элементы последовательности четные, для всех поэтому

Итак, согласно последнему пункту, у числа делится хотя бы на 100 различных простых чисел. А согласно второму пункту,