I write the number $6$ on the blackboard. At the $n^\text{th}$ step, an integer $k$ on the board is replaced by $k + \gcd(n, k)$. Prove that at each step, the number on the blackboard increases either by $1$ or by a prime number.
These are something I have tried: Actually, I have no idea for this question but I noticed that The difference can't be equal to $2$