SIMON-MARAIS 2021 A2

Define the sequence of integers $a_1, a_2, a_3, \ldots$ by $a_1 = 1$ , and $$a_{n+1} = \left(n+1-\gcd(a_n,n) \right) \times a_n$$ for all integers $n \ge 1$ . Prove that $\frac{a_{n+1}}{a_n}=n$ if and only if $n$ is prime or $n=1$ . Here $\gcd(s,t)$ denotes the greatest common divisor of $s$ and $t$ .