Proviamo!
Innanzitutto la tesi è vera per $p=3$, dato che $a_1 =4$. Pongo $b_i = \displaystyle \frac{a_i +2}{2}$. Poichè $a_i = 2b_i -2$, la ricorrenza diventa:
$2b_{n+1} -2 = 2b_{n} -2 + 2b_{n-1} -2 + \frac{1}{2}(2b_n -2)(2b_{n-1} -2) \longrightarrow b_{n+1} = b_n + b_{n-1} -1 +b_nb_{n-1} -b_n -b_{n-1} +1 = b_nb_{n-1}$
Vale quindi:
\[
\left\{
\begin{array}{l}
b_0 = 2 \\
b_1 = 3\\
b_{n+1} = b_nb_{n-1}
\end{array}
\right.
\]
Ora, sia $F_n$ l'$n$-esimo numero di Fibonacci, con $F_0 = 0, F_1 = 1$. Si dimostra facilmente per induzione che per $n \geq 1$, vale $\displaystyle b_n = 3^{\displaystyle F_n} \cdot 2^{\displaystyle F_{n-1}} $. Allora, per $p > 3$:
\[
a_q \equiv 1 \pmod p \Leftrightarrow 2b_q \equiv 3 \pmod p \Leftrightarrow \displaystyle 3^{\displaystyle F_q} \cdot 2^{\displaystyle F_{q-1} +1} \equiv 3 \pmod p \Leftrightarrow 3^{\displaystyle F_q -1} \cdot 2^{\displaystyle F_{q-1} +1} \equiv 1 \pmod p
\]
Dimostro che per ogni $p$, esiste $q$ t.c. $p-1 \mid F_q -1$ e $p-1 \mid F_{q-1} +1$.
E' abbastanza noto ed è stato dimostrato anche qui non troppo tempo fa che $\forall n \in \mathbb{N}$ i numeri di Fibonacci sono periodici modulo $n$, senza antiperiodo. Pertanto lo sono anche modulo $p-1$: in particolare, esiste $m > 2$ t.c. $F_m \equiv 0 \pmod{p-1}$ e $F_{m+1} \equiv 1 \pmod{p-1}$. Ma allora $F_{m-1} \equiv 1$ e $F_{m-2} \equiv -1$, pertanto $q = m-1$ realizza le divisibilità che volevamo. A questo punto:
\[
a_q \equiv 1 \pmod p \Leftrightarrow 3^{\displaystyle F_q -1} \cdot 2^{\displaystyle F_{q-1} +1} \equiv 1 \pmod p
\]
e la seconda congruenza è vera per il Piccolo Teorema di Fermat, dato che gli esponenti sono multipli di $p -1$, quindi è vera anche la prima congruenza, che è la tesi.
