Q2 Matemática  (Simon Marais Mathematical Competition 2021)

Defina a sequência de inteiros $a_1,a_2,a_3,\dots$ por $a_1=1$ e $$a_{n+1}=\left(n+1-\gcd (a_n,n)\right)vezes{a}_n$$para todos os inteiros $n\ge 1$. Prove que $\frac{a_{n+1}}{a_n}=n$ se e somente se $n$ for primo ou $n=1$. Aqui $\gcd (s,t)$ denota o máximo divisor comum de $s$ e $t$.