Числа Фибоначчи и делимость

[Ktina]

Доказать, что $F_{25n}$ делится на 25 при любом натуральном $n$.

Можно, конечно, вычислить вручную 25-ое число Фибоначчи (если не ошиблась, оно равно 75025), а затем легко доказать по индукции то, что требуется.
Можно ещё и не само число вычислять, а только две последние цифры, так быстрее.

Но вряд ли на олимпиаде требовалось именно это (хотя оно и не трудно).
Может, есть какой-то обходной путь, чтобы само число (или его цифры) не считать?

[Null]

Ну наверное взять формулу Бине и раскрыть в ней скобки. Там почти все слагаемые будут делиться на 25.

[ИСН]

Считать сразу по модулю 25.

-- Пт, 2012-02-10, 20:34 --

1,1,2,3,5,
8,13,21,9,5,
14,19,8,2,10,
12,22,9,6,15,
21,11,7,18,0

-- Пт, 2012-02-10, 20:40 --

Альтернатива - разработать теорию пизанских периодов (Pisano periods), конкретно - ту её часть, где переход от простых к степеням простых, а для 5 посчитать руками. Но это не проще.