Let $a_n=(n^2-n)b_n+2n-2$. We get $(n-1)a_{n+1}=(n-1)((n+1)^2-(n+1))b_{n+1}$ $+(2(n+1)-2)(n-1)=(n-1)n(n+1)b_{n+1}+2n(n-1)$ and $(n+1)a_n-2(n-1)=(n^2-n)(n+1)b_n+(2n-2)(n+1)$ $-2n+2=(n-1)n(n+1)b_n+2n^2-2n$ so that means that $b_n=b_{n+1}$ is a constant. So $a_n=cn^2-cn+2n-2=(cn+2)(n-1)$, where to make $a_n$ an integer we need $2c$ to be an integer. So then $2000|a_{1999}$, so $2000|(1999c+2)(1999-1)$ and so $2000|1999(2c)+4$. Thus $2c\equiv4\mod 2000$ and $c\equiv 2\mod 1000$. So then $c=2+1000k$ and $a_n\equiv 0\mod 2000\Rightarrow (2n+1000kn+2)(n-1)\equiv0\mod2000$ $\Rightarrow 2000k\frac{n^2-n}{2}+2(n^2-1)\equiv0\mod2000\Rightarrow n^2\equiv1\mod1000$ $\Rightarrow n\equiv\pm1\mod250$. So $n=249$ is the first one that could work. And $a_{249}=((2+1000k)249+2)(248)=249\cdot124\cdot2000k+500\cdot248\equiv0\mod2000$ so it does in fact work.

we have \[ \frac{a_{n+1}}{(n+1)n}-\frac{2}{n+1}=\frac{a_n}{n(n-1)}-\frac{2}{n} \] and \[ a_n=c\frac{n(n-1)}{2}+2(n-1) \] where, $c=a_2-2\in Z$. Since $2000|a_{1999}$ we get $2000|999c+4$ and $c\equiv 4 \pmod{2000}$. We get easily $n_{min}=249$.

Let $a_n=b_n+2(n-1) $ . Plugging it in this equation gives, $n(b_{n+1}-b_{n})=b_n+b_{n+1} \implies \frac{b_{n+1}}{b_n}=\frac{n+1}{n-1}$.And this is true for all $n \ge 2$. Putting, $n=2,3,.....,n$ and multiplying gives a telescopic product which gives $b_n = \frac{n(n-1)}{2}b_2$. Thus we have $a_n = \frac{n(n-1)}{2}b_2+2(n-1)$. Since $a_{2009} \equiv 0 \pmod{2000} \implies b_2 \equiv 4 \pmod{2000}$. And this gives minimial possible $n$ satisfying $2000|a_n$ as $249$. Thus $249$ is the answer $\blacksquare$.