Brazilian Math Olympiad

The answer is yes and you can construct an example in several ways. The main observation is that $\gcd (a_i,a_j)=a_j-a_i⟺a_j-a_i\mid a_i$. In fact, if $\gcd (a_i,a_j)=a_j-a_i$ then $a_j-a_i\mid a_i$ and, conversely, if $a_j-a_i\mid a_i$ then $a_j-a_i\mid a_i+(a_j-a_i)⟺a_j-a_i\mid a_j$, so $a_j-a_i\mid \gcd (a_i,a_j)$. But $\gcd (a_i,a_j)\mid a_i$ and $\gcd (a_i,a_j)\mid a_j$ implies $\gcd (a_i,a_j)\mid a_j-a_i$, so $\gcd (a_i,a_j)=a_j-a_i$.

Once this fact is established, one can construct the sequence inductively as follows: first consider the two-term sequence $(1,2)$. Now, given a sequence $(x_1,x_2,\dots ,x_{k-1})$ with $k-1$ terms such that $\gcd (x_i,x_j)=x_j-x_i$, construct a new sequence adding $x_0$ to every term and putting $x_0$ at its beginning: $(x_0,x_1+x_0,x_2+x_0,\dots ,x_{k-1}+x_0)$. All we need to do is to find $x_0$. By the previous observation, we need $x_j-x_i\mid x_i+x_0$ and $x_i\mid x_0$. We already have that $x_j-x_i\mid x_i$, so a good choice is $x_0=\mathrm{lcm}(x_1,x_2,\dots ,x_{k-1})$, because by definition $x_i\mid x_0$ and, since $x_i\mid x_0$ and $x_j-x_i\mid x_i$, $x_j-x_i\mid x_0$, so $x_j-x_i\mid x_i+x_0$. So we obtained a new sequence with $k$ terms and the result follows by induction.