Beatiful problem ! Define $b_n=a_n+2$. Easy to see that $b_n=\frac{b_{n-1}b_{n-2}}{2}$. $b_0=4, b_1=6$. Obvious conclusion is that each $b_n$ is fo the form $2^x 3^y$. Now we can check that $b_m=2^{F_{m-1}+1}3^{F_m}$, where $F$ is Fibonacci's sequence. We will prove that every prime $p>2$ satisfies the condition. Let $p>3$ (for $p=3$ it's trivial). $a_m-1=b_m-3=3 \cdot (2^{F_{m-1}+1}3^{F_m-1} -1)$. Using Fermat's Little Theorem we know that if $p-1|F_{m-1}+1$ and $p-1|F_m-1$ we will be done. But we know that if a pair of 2 consecutive Fibonacci's numbers is mod $p-1$ equal to $(a, b)$, it determines next and previous pair mod $p-1$, so if we consider pairs mod $p-1$ as vertices and put edge between $(a, b)$ and $(b, a+b)$, it forms cycle covering. We have to prove that pair $(-1, 1)$ lies on the same cycle as $(F_0, F_1)$. But this is true, because there's edge from $(-1, 1)$ to $(1, 0)$ and edge from $(1, 0)$ to $(0, 1)$.

Swistak wrote: Beatiful problem ! Define $b_n=a_n+2$. Easy to see that $b_n=\frac{b_{n-1}b_{n-2}}{2}$. $b_0=4, b_1=6$. Obvious conclusion is that each $b_n$ is fo the form $2^x 3^y$. Now we can check that $b_m=2^{F_{m-1}+1}3^{F_m}$, where $F$ is Fibonacci's sequence. We will prove that every prime $p>2$ satisfies the condition. Let $p>3$ (for $p=3$ it's trivial). $a_m-1=b_m-3=3 \cdot (2^{F_{m-1}+1}3^{F_m-1} -1)$. Using Fermat's Little Theorem we know that if $p-1|F_{m-1}+1$ and $p-1|F_m-1$ we will be done. But we know that if a pair of 2 consecutive Fibonacci's numbers is mod $p-1$ equal to $(a, b)$, it determines next and previous pair mod $p-1$, so if we consider pairs mod $p-1$ as vertices and put edge between $(a, b)$ and $(b, a+b)$, it forms cycle covering. We have to prove that pair $(-1, 1)$ lies on the same cycle as $(F_0, F_1)$. But this is true, because there's edge from $(-1, 1)$ to $(1, 0)$ and edge from $(1, 0)$ to $(0, 1)$. I don't understand. Can You say clear?

When a,b={0,1,...,p-1} ,number of (a,b) pairs is p^2 . If we write first p^2+1 terms of the sequence of (a,b)s , then we can find same 2pairs from the sequence has a period. So there exists a term (a,b) for which a and b remain 1,0 by mod p-1 respectively .because first term of the sequence is (1,0) . Then the previous of (a,b) is (-1,1) .

Basically, we have: \begin{align*} a_{n+1} = \frac{a_n a_{n-1}}{2} + a_n + a_{n-1} \\ 2a_{n+1} = a_na_{n-1} +2a_n+2a_{n-1} \\ 2(a_{n+1}+2) =(a_n+2)(a_{n-1}+2) \\ \frac{ a_{n+1}+2}{2} = \frac{a_n+2}{2} \cdot \frac{a_{n-1}+2}{2} \end{align*}Setting $b_k = \frac{a_k+2}{2}$ gives us that $b_{n+1} = b_nb_{n-1}$ with $b_0=2$ and $b_1 =3$. Now by trivial induction we can obtain that: $$ b_n =2^{F_{n-2}}3^{F_{n-1}}$$where $F_n$ is the $n$-th Fibanocci number. This implies that: $$ a_n -1 =2(2^{F_{n-2}+1}3^{F_{n-1}-1}-1) $$The problem is solved by Fermat's theorem if we are able to find such $n$ that $p-1 \mid F_{n-2}+1$ and $p-1 \mid F_{n-1}-1$. The key idea that Fibanocci sequence is periodic $\pmod {p-1}$ as there is only $(p-1)^2$ pairs of residues $(F_k, F_{k+1})$ and every pair uniquely determines the next one. Since Fibannoci sequence have a pair $(1,1)$, then: $$ (-1,1) \rightarrow (1,0) \rightarrow (0,1) \rightarrow (1,1) $$meaning that is has a pair $(-1,1)$ too, which solves the problem.