BULGARIAN NATIONAL MATHEMATICAL OLYMPIAD

Let $a$ be the smallest number on the board such that $(m+1)a>N$. It is easy to see that $a=\frac{m^{2017}+m^2+m+1}{m+1}$. We will prove that $a$ is the last deleted number.

The numbers $2a,3a,\dots ,ma$ are not on the board since they are not congruent $1$ modulo $m$. Therefore $a$ can not be deleted as divisor (i.e. before we reach it).

Let $b<a$ is one of the numbers on the board in the beginning. It is enough to prove that there exists a number $c>a$, which is multiple to $b$ and $c$ is on the board. Let $b_0=b$, $b_{k+1}=(m+1)b_k$ for $k\ge 0$. Since $b_k\equiv b_0\equiv 1(\mathrm{mod}m)$, all numbers $b_k\le N$ are on the board in the beginning. Let $i$ be such that $b_{i-1}<a\le b_i$. If $a<b_i$, then $b\mid b_i=(m+1)b_{i-1}\le N$. If $a=b_i$, then $$a+m{b}_{i-1}=\frac{(2m+1)a}{m+1}$$ is divisible by $b$ and is on the board in the beginning since it is less than $$2a=\frac{2(m^{2017}+m^2+m+1)}{m+1}<N.$$