It is easy to prove that $a_{n+1}= a_{1}a_{2}...a_{n}+k$ and that $\gcd(a_{i}; k) =1$ (because $a_{1}= k+1$) [Moderator's edit: I see you are a bit lazy dear Lopes :razz: ;anyway I am completing bellow your solution ] We have that $a_{n+1}=a_{n}^{2}-ka_{n}+k$, then $\frac{a_{n+1}-k}{a_{n}-k}=a_{n}$ ,therefore \[\prod_{i=1}^{n+1}{\frac{a_{i}-k}{a_{i-1}-k}}=\prod_{i=1}^{n}a_{n}\Leftrightarrow a_{n+1}-k=a_{n}a_{n-1}...a_{1}\] thus $a_{n+1}=a_{n}a_{n-1}...a_{1}+k$ as was clamed above. Also we have that if $a_{m}\equiv 1(\mod{k})$ then $a_{m+1}=a_{m}^{2}-ka_{m}+k\equiv 1-k+k \equiv 1(\mod{k})$ and since $a_{1}\equiv 1 (\mod{k})$ then $a_{n}\equiv 1(\mod{k})$ for any positive integer $n$. As a result we have that $\gcd(a_{n};k)=1$ for any $n$. And because $a_{n+1}=a_{n}a_{n-1}...a_{1}+k$, then $\gcd(a_{n+1};a_{n}a_{n-1}...a_{1})=1$, so $\gcd(a_{m};a_{n})=1$ for all different positive integer numbers $m$ and $n$.

Let $p$ be a prime dividing $a_n$ and $a_m$ where $m<n$. Then $a_{m+1} \equiv k \pmod p$ which means that $a_{m+i} \equiv k \pmod p$ for all $i \geq 1$. In particular $a_n \equiv k \pmod p$ which means $p$ divides $k.$ So, $a_1 \equiv 1 \pmod p$ which means that $a_j \equiv 1 \pmod p$ for all $j \geq 1$ which is a contradiction.

we will prove by induction $a_{n+1}=a_1\cdot \cdot \cdot a_n+k$ $a_2=a_1^2-a_1\cdot k+k=(k+1)^2-(k+1)\cdot k+k=2k+1=a_1+k$ $a_{n+1}=a_n(a_n-k)+k=a_n(a_1\cdot \cdot \cdot a_{n-1})+k$ so the induction is proved so if $m<n$ so by the thing we proved we know that $gcd(a_m,a_n)=gcd(a_n,k)$ and the$ gcd(a_n,k)=gcd(a_n,a_{n-1})=....=gcd(a_2,a_1)=gcd(2k+1,k+1)=1$ and we are done