Районная олимпиада, 2003-2004 учебный год, 10 класс

В последовательности $U_1,~ U_2, ~U_3, ~\ldots, ~U_1 = U_2 = 1$, а каждое число, начиная с третьего, есть сумма квадратов двух предыдущих. Делится ли $U_{2003}$ на 7?

Комментарий/решение

$U_n=\{1,1,2,5,29,866,750797,563696885165,\ldots\}$

Рассмотрим следующую последовательность:

$U_n \pmod{7} = \{1,1,2,5,1,5,5,1,\ldots \}$

Легко заметить, что в данной последовательности нет нулевых остатков, значит $7\nmid U_{2003}$.