Высшая проба 2020, 9-10 классы, задача 3
( баллов) В последовательности чисел Фибоначчи , , , , , , , , каждое следующее число, начиная с третьего, равно сумме двух предыдущих. Докажите, что среди чисел Фибоначчи нет ни одной натуральной степени числа .
Доказательство. Для начала докажем, что на делятся те и только те числа Фибоначчи, номер которых
делится на . Докажем это по индукции.
База: Первое число Фибоначчи, кратное - это , которое является числом Фибоначчи.
Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от до . Докажем, что он верен
для чисел от до . Пусть число с номером имело остаток от деления на (). Тогда
числа с номерами , , будут иметь следующие остатки: , , , , , , , .
Теперь докажем, что на делятся те и только те числа Фибоначчи, номер которых делится на . Доказательство аналогично.
Следовательно, если число Фибоначчи делится на , то его номер делится на . Значит его номер делится
на , а значит, само число обязано делиться на . Значит оно не может быть равно натуральной степени
числа .
− Перебор конечного числа чисел Фибоначчи.
∓ Доказано, что на 7 делятся те и только те числа Фибоначчи, номер которых делится на 8.