Nemotron-IMO-Bench 2026 N41

Let $(a_n)_{n\geq 0}$ be a sequence such that $a_0=6$ and for $n>0$ $$a_n=a_{n-1}+\gcd(a_{n-1}, n).$$ Prove that for all $n$ the number $a_n-a_{n-1}$ is either $1$ or a prime number.