Найти все простые в последовательности

[Ktina]

Дана последовательность, первый член которой равен 2, второй равен 3, а каждый следующий задан формулой $a_{n+1}=a_na_{n-1}-a_n-a_{n-1}+2$.
Найти все простые числа в этой последовательности, обосновав свой ответ.
(British Mathematical Olympiad)

[hippie]

Ответ: $a_1=2;\ a_2=3;\ a_3=3;\ a_4=5;\ a_7=257.\ $

$a_n=2^{F_{n-1}}+1,$ где $F_k$ — $k$-е число Фибоначчи.
Заметим, что если $p$ имеет нечётный делитель $q(>1),$ то $2^p+1$ кратно $2^{\frac pq}+1,$ и, следовательно, не может быть простым числом.

[nnosipov]

Надо ещё объяснить, почему других чисел Фибоначчи, являющихся степенями двойки, нет. Можно, например, так: если какое-то число Фибоначчи делится на $16$, то оно делится на $3$.