Problem

Source: St Petersburg Olympiad 2011, Grade 11, P5

Tags: number theory



Let $M(n)$ and $m(n)$ are maximal and minimal proper divisors of $n$ Natural number $n>1000$ is on the board. Every minute we replace our number with $n+M(n)-m(n)$. If we get prime, then process is stopped. Prove that after some moves we will get number, that is not divisible by $17$