Q45 Matemática  (Tournament Of Towns 2009)

Inicialmente, um número $6$ é escrito em um quadro-negro. No passo $n$-ésimo, um inteiro $k$ no quadro-negro é substituído por $k+gcd(k,n)$. Prove que a cada passo o número no quadro-negro aumenta em $1$ ou em um número primo.