If $d$ is the relevant greatest common divisor, then $a_{1000}=a_{999}^{2}+1 \equiv 1=a_{0}(\bmod d)$, which implies (by induction) that the sequence is periodic modulo $d$, with period 1000 . In particular, $a_{4} \equiv a_{2004} \equiv 0$. So $d$ must divide $a_{4}$. Conversely, we can see that $a_{5}=a_{4}^{2}+1 \equiv 1=a_{0}$ modulo $a_{4}$, so (again by induction) the sequence is periodic modulo $a_{4}$ with period 5 , and hence $a_{999}, a_{2004}$ are indeed both divisible by $a_{4}$. So the answer is $a_{4}$, which we can compute directly; it is 677.