Числа Фибоначчи

[arqady]

Как легче всего понять, что каждое сто двадцать пятое число Фибоначчи делится на 125?
Например, можно доказать, что

$$F_{5n}=25F_n^5+25(-1)^nF_n^3+5F_n$$

и из этого всё следует, но это, по моему, очень сложно.
Спасибо!

[lel0lel]

$F_k\mid F_{m k}$

[Null]

Считать $F_{125}$ не радостно. Проще взять формулу Бине. Там почти все делиться на 125.

[Andrey A]

О делимости Фибоначчи на степени простых что-то не помню где было. Надо погуглить. Если $F_{125}$ делится (а оно делится), то конечно $F_{125n}$ тоже делится - вопрос о первом номере вхождения кратного. Чтобы сделать выводы из приведенной формулы, тоже надо знать, что $F_{25}$ делится на $25$. Но если каждое четвертое делится на $3$, каждое двенадцатое - на $9$, то каждое какое делится на $27$? Хотя, пятерка для Фибоначчи, конечно, отдельный случай.