Теория чисел на Высшей пробе

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

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от до Докажем, что он верен для чисел от до Пусть число с номером имело остаток от деления на Тогда числа с номерами будут иметь следующие остатки:

Теперь докажем, что на делятся те и только те числа Фибоначчи, номер которых делится на Доказательство аналогично.

Следовательно, если число Фибоначчи делится на то его номер делится на Значит его номер делится на а значит, само число обязано делиться на Значит оно не может быть равно натуральной степени числа