Задача М1275‍‍‍

Пусть $k\gt8$‍.‍ Будем рассматривать остатки от деления чисел $a_i$‍,‍ $i\gt k-6$‍,‍ на $m=a_{k-6}$‍.‍ Мы используем запись $a\equiv b\pmod m$‍‍ для обозначения того, что числа $a$‍‍ и $b$‍‍ дают одинаковый остаток при делении на $m$‍,‍ и пользуемся тем, что остаток суммы (и произведения) равен остатку суммы (соответственно произведения) остатков этих чисел (см. статью А. Егорова в «Кванте» № 6, 1991).

Поскольку $$ a_{k-5}=a_{k-6}a_{k-7}+1\equiv1\pmod m $$ и $$ a_{k-4}=a_{k-5}a_{k-6}+1\equiv1\pmod m, $$ то $$\begin{gather*} a_{k-3}=a_{k-4}a_{k-5}+1\equiv2\pmod m,\\ a_{k-2}=a_{k-3}a_{k-4}+1\equiv3\pmod m,\\ a_{k-1}=a_{k-2}a_{k-3}+1\equiv7\pmod m,\\ a_k=a_{k-1}a_{k-2}+1\equiv22\pmod m. \end{gather*}$$ Откуда следует, что $a_k-22$‍‍ делится на $a_{k-6}$‍.‍ Конечно, точно так же можно доказать, что (начиная с некоторого $k$‍)‍ будут составными и числа $a_k-b$‍,‍ где $b$‍‍ — любое другое число последовательности 1, 1, 2, 3, 7, 22, $\ldots$‍,‍ определяемой тем же рекуррентным соотношением: каждое число на 1 больше произведения двух предыдущих.