Делимость и делители (множители) → .08 Теоретико-числовые свойства чисел Фибоначчи

Решим сначала уравнение

______________________________________________________________________________________________________________________________________________________

Умножим на 4 и прибавим 1 к обеим частям, чтобы выделить полный квадрат справа:

Теперь домножим обе части на 5 и выделим полный квадрат слева:

Сделаем замену . У получившегося уравнения

имеются решения

где — числа Фибоначчи (мы пользуемся нумерацией при всех целых ). На самом деле

равно для всех , что легко проверить по индукции: при это выполняется, а если , то и

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

Теперь нужно найти бесконечно много и таких, для которых соответствующие и целые. Заметим, что последовательность остатков чисел Фибоначчи по модулю 10 периодична (так как пара ( ) может принимать конечное количество вариантов по модулю 10, а остаток следующего и предыдущего чисел Фибоначчи однозначно определяются по остаткам этой пары). Кроме того, и подходят, они соответствуют тривиальному решению . Значит, уравнение имеет бесконечно много решений.

_________________________________________________________________________________________________________________________________________________________________________________

Осталось понять, что они все не могут обнулять знаменатель. Действительно, если — решение уравнения , при котором , то и . Следовательно, . Так как целое, то обязательно (иначе ), а значит, и . Остальные пары нам подходят.

(a) Запишем последовательность чисел Фибоначчи в системе остатков по модулю 5:

В последовательности Фибоначчи каждое число определяется двумя предыдущими, поэтому, если пара последовательных чисел повторится, последовательность станет циклической. Тогда длина предпериода или периода не может превышать Остаётся проверить, появится ли в периоде остаток 0 по модулю 5. Выше уже выписана последовательность; можно заметить, что период равен 20 и в нём содержится остаток 0. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 5.

(b) Будем рассматривать числа последовательности Фибоначчи по модулю 2024. Из пункта (a) понятно, что здесь также будет период, и его длина не более Назовём состоянием пару последовательных чисел. Состояние однозначно определяет следующее число — и предыдущее — Это означает, что предпериода нет, так как в каждое состояние мы однозначно попадаем из состояния Значит, период начинается с Пусть последний остаток в периоде равен тогда:

Но так как то и есть искомое число, кратное 2024. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 2024.

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

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

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

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

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

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

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

Отметим, что число в силу предыдущего пункта, так как Предположим, что для некоторого простого и В силу предыдущего пункта, откуда либо либо либо так как Значит, либо либо Однако, если то поэтому никакие из заведомо не подходят. Непосредственная проверка показывает, что только удовлетворяет соотношению

Применим трижды тождество

сначала к и паре а затем к c парой и к c парой

Для завершения доказательства осталось проверить, что Разложим левую часть на две скобки по формуле разности кубов, тогда вторые скобки в левой и правой части сразу совпадут, а первые будут равняться так как

Рассмотрим произвольное представление произвольного числа описанное в задаче. Если  – его наибольшее слагаемое, то докажем, что Будем доказывать это утверждение индукцией по База очевидна. Теперь покажем переход. Действительно, равносильно Рассмотрим представление числа полученное из представления вычеркиванием слагаемого Согласно условию задачи, оно не содержит слагаемого поэтому его наибольшее слагаемое не превосходит откуда, по предположению индукции, что и требовалось доказать.

Из доказанного утверждения немедленно следует единственность. Действительно, пусть у какого-то существует два различных представления. Сократим все их общие слагаемые. Так как представления различны, сократятся не все слагаемые, и мы получим два представления некоторого числа удовлетворяющих условию задачи, наибольшие слагаемые которых различны. Пусть в одном наибольшее слагаемое это а в другом Тогда, согласно утверждению, хотя  – противоречие.

Существование представления практически очевидно. Если то возьмем в представление слагаемое а дальше рекурсивно построим представление для Ясно, что поэтому наибольшее слагаемое его представления не превосходит поэтому полученное представление для тоже удовлетворяет условию задачи.

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

Для и это верно.

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

Алгоритм отгадывания числа ясен из предыдущих рассуждений: на каждом шаге множество из чисел, содержащее загаданное число, нужно разбивать на множества из чисел и из чисел, и задавать вопрос о принадлежности числа множеству

Введем обозначение Фактически, задача свелась к доказательству того, что для всех Проведем доказательство по индукции по парам чисел База индукции тривиальна для всех Теперь допустим, что для всех где , кроме пары утверждение уже доказано; покажем утверждение для Для этого снова вспомним тождество

С помощью него получим, что

Поскольку по предположению индукции и получаем что и что и требовалось доказать.

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

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

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

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

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

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

Чтобы найти остаток при делении на достаточно знать остаток при делении на потому что

По индукции доказывается, что остатки при делении чисел Фибоначчи на повторяются с периодом

Поскольку делится на с остатком имеем

Предположим, что найдутся два не взаимно простых соседних числа Фибоначчи и . Обозначим их НОД через . Тогда предыдущее число Фибоначчи также делится на . Рассуждая аналогично, дойдём до начала последовательности Фибоначчи и получим, что все числа делятся на . Но тогда и делится на , откуда , противоречие.