В последовательности чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, . . . каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа 7.
Для начала докажем, что на 7 делятся те и только те числа Фибоначчи, номер которых делится на 8. Докажем это по индукции.
База: Первое число Фибоначчи, кратное 7 – это 21, которое является 8 числом Фибоначчи. Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от 1 до 8k. Докажем, что он верен для чисел от 8k + 1 до 8k + 8. Пусть число с номером 8k − 1 имело остаток a от деления на 7 (
). Тогда числа с номерами 8k + 1, . . . , 8k + 8 будут иметь следующие остатки: a, a, 2a, 3a, 5a, a, 6a, 0.
Теперь докажем, что на 3 делятся те и только те числа Фибоначчи, номер которых делится на 4. Доказательство аналогично.
Следовательно, если число Фибоначчи делится на 7, то его номер делится на 8. Значит, его номер делится на 4, а значит, само число обязано делиться на 3. Значит, оно не может быть равно натуральной степени числа 7.