Let ${\bf S}$ be the set of integers satisfying the given conditions, and assume $N \! \in {\bf S}$. If $k$ is even and $r_k$ is even, then $N$ is even because $N=q_kk+r_k$ for some integer $q_k$. Thus $r_k$ is odd when $k$ is even. Let $p$ be the unique integer for which $r_p = 0$. If $p$ is composite, there exists a prime $q<p$ which divides $p$, implying $r_q=0$. This contradition yields $p$ is a prime. Now $r_2=1$ since $N$ is odd, thus $p \neq 2$. The fact that $0 \leq r_k \leq k-1$ implies $r_3=2$ since $0=r_p$, $1=r_2$, which again implies $r_4=3$, $r_5=4$, ... , $r_{p-1}=p-2$. So this inductive argument gives $(1) \, r_k = k-1, \; 2 \leq k \leq p-1.$ First assume $p < 500$. Thus $2p < 1000$. Now $r_p=0$ implies $p|r_{2p}$, implying $r_{2p}= p$ since $r_{2p} < 2p$ and $r_{2p} \neq r_p = 0$. This combined with (1) and the fact that $r_{p+1} \in \{0,1,2, \ldots, p\} = \{r_p,r_2,r_3, \ldots, r_{p-1}\} \cup \{p-1\} \cup \{r_{2p}\}$ yields $r_{p+1}=p-1$ because $r_i \neq r_j$ when $i \neq j$. But $r_{p+1}$ is odd since $p$ is a odd prime, hence $r_{p+1}=p-1$ is a contradition which implies $p > 500$. Next assume $500 < p < 1000$. For the positive integers $k \leq p$ define the odd positive integer $N_k = \frac{1000!}{p}k - 1$. Futhermore, let $m$ be an integer such that $2 \leq m \leq 1000$ and $m \neq p$. Clearly $m|\frac{1000!}{p}$, hence $N_k \equiv - 1 \equiv m-1 \pmod{m},$ i.e. the remainder is $m-1$ when $N_k$ is divided by $m$. Assume $a$ and $b$ are integers such that $1 \leq a < b \leq p$ and $N_a \equiv N_b \pmod{p}$ $\Rightarrow \; \frac{1000!}{p}a - 1 \equiv \frac{1000!}{p}b - 1 \pmod{p}$ $\Rightarrow \; \frac{1000!}{p}(b-a) \equiv 0 \pmod{p}$ $\Rightarrow \; 1000!(b-a) \equiv 0 \pmod{p^2}.$ Now $1 \leq a < b \leq p$ implies $0 < b - a < p$, hence $p \!\! \not | \, b-a$. Also $p \!\! \not | \, \frac{1000!}{p}$ because $p > 500$ yields $1000 < 2p < p^2$, meaning $p^2 \!\! \not | \, 1000!$. Consequently $N_a \not \equiv N_b \! \pmod{p}$, so $N_1$, $N_2, \ldots , N_p$ is congruent to $0, 1, 2, \ldots ,p-1$ modulo $p$ in some order. Therefore there in one unique integer $c \in \{1,2, \ldots, p\}$ such that $N_c \equiv 0 \pmod{p}$. Summa summarum $N_c$ has 999 distinct remainders when divided by $2, 3, \ldots ,1000$ and one of them is zero. Hence $N_c \! \in {\bf S}$, which lead us to the following conclusion: The values of $k$ for which is it possible that $r_k = 0$, are all primes between 500 and 1000. q.e.d.