Mathematical Olympiad Rioplatense

Let $N$ be the odd integer; then the first remainder $r_2$ equals $1=2-1$. Next, $r_j=j-1$ cannot hold for all $j$ or else no $r_j$ is $0$. Let $k>2$ be the first number such that $r_k\ne k-1$. Then $r_j=j-1$ for $j=2,\dots ,k-1$, so $r_k\ne 1,2,\dots ,k-2$ because the $r_j$ are pairwise distinct. On the other hand $0\le r_k\le k-1$,

hence $r_k\ne k-1$ implies $r_k=0$. Thus remainder $0$ is obtained upon division by the least $k$ such that $r_k\ne k-1$. Observe now that $k$ is a prime. If $d$ is a proper divisor of $k$ then $2\le d<k$, hence $r_d=d-1$ by the minimality of $k$. However $d$ divides $k$ and $k$ divides $N$ (as $r_k=0$), so $d$ divides $N$, yielding $r_d=0$ which is false. So $k>2$ is a prime. Next we show that $k>500$. Suppose not; then $2k\le 1000$ and we determine $r_{2k}$ directly. Since $k$ divides $N$ and $N$ is odd, one can write $N=(2s+1)k$ for some integer $s$. Then $N=s(2k)+k$ and because $0<k<2k$, it follows that $r_{2k}=k$. However look also at $r_{k+1}$. It is different from $0,1,\dots ,k-2$ (the remainders $r_2,r_3,\dots ,r_k$) and does not exceed $k$. Because $k+1\ne 2k$ and $r_{2k}=k$, the only remaining possibility is $r_{k+1}=k-1$. Hence $N=q(k+1)+(k-1)$ for some integer $q$. But $k+1$ and $k-1$ are both even as $k$ is odd; so $N$ is even which is a contradiction. We proved that $k$ is a prime greater than $500$. Conversely, every prime $p\in (500,1000)$ serves the purpose for a suitable odd $N$. Let $M$ be the least common multiple of $2,3,\dots ,p-1,p+1,\dots ,1000$. Consider $Mx-1$ for $x=1,2,3,\dots$. Because $p$ is coprime to $M$ due to $2p>1000$, there is an $x$ such that $Mx-1$ is divisible by $p$. Set $N=Mx-1$, then $p$ divides $N$, so $r_p=0$. Also each $j=2,3,\dots ,p-1,p+1,\dots ,1000$ divides $M$ and hence also $N+1$. Thus $N$ is congruent to $-1$ modulo $j$, meaning that $r_j=j-1$. The numbers $r_2,r_3,\dots ,r_{1000}$ are pairwise distinct and one of them is $0$. The answer is: all primes between $500$ and $1000$.