Nice problem! Let $P(n): a_na_{n+2}=a_{n+1}^2+p$ Then $P(n),P(n+1) \Rightarrow a_{n+1}a_{n+3}-a_na_{n+2}=a^2_{n+2}-a^2_{n+1}\Leftrightarrow a_{n+1}(a_{n+1}+a_{n+3})=a_{n+2}(a_{n+2}+a_n)$ Set $d=gcd(a_{n+1},a_{n+2})$, then $d|a_{n+1}a_{n+3}-a_{n+2}^2=p$ so $d=1\,\,\,or\,\,\,d=p$ If $d=p$ then $P(n+2): a_{n+2}a_{n+4}=a^2_{n+3}+p\pmod p\Leftrightarrow p|a_{n+3}$ so $P(n+1): a_{n+1}a_{n+3}=a^2_{n+2}+p\pmod p^2\Leftrightarrow p^2|p$, contradiction! So $d=1$ and $a_{n+1}|a_{n+2}(a_{n+2}+a_{n})\Rightarrow a_{n+1}|a_n+a_{n+2}$ QED

We have $a_na_{n+2}=a_{n+1}^2+p$ and $a_{n+1}a_{n+3}=a_{n+2}^2+p$. Therefore, $$a_na_{n+2}-a_{n+1}^2=a_{n+1}a_{n+3}-a_{n+2}^2 \iff a_{n+2}(a_n+a_{n+2})=a_{n+1}(a_{n+1}+a_{n+3}).$$Suppose $d=\gcd(a_{n+1},a_{n+2})>1$. Then $d\mid a_na_{n+2}-a_{n+1}^2=p$ and since $d>1$, we get $d=p.$ Now $$a_{n+2}a_{n+4}-a_{n+3}^2=p$$and since $d\mid a_{n+2}$, we get $d\mid a_{n+3}.$ Thus, $$p=a_{n+1}a_{n+3}-a_{n+2}^2\equiv 0\pmod{p^2},$$which is impossible. Hence $d=\gcd(a_{n+1},a_{n+2})=1$, so $a_{n+1}\mid a_n+a_{n+2}$ and we are done.