Problem from Russia 1995 (also in Art anf Craft)

[Avik Roy]

The sequence $a_1, a_2, ... $ of natural numbers satisfy the relation: $(a_i,a_j)=(i,j)$ for $i \ne j$ where $(m,n)$ for natural numbers $m$ and $n$ denote the GCD of $m$ and $n$. Prove that $a_i = i$ for all $i$

[Avik Roy]

the problem statement has been corrected, the condition $i \ne j$ was missing earlier

[Masum]

First see that the sequence contains distinct integers,that is $a_i\neq a_j$ for $i\neq j$
Set $i=1,gcd(a_j,a_1)=1\forall i$,so $a_1$ must be $1$ because otherwise there must be an $a_k$ such that $a_1$ shares a common prime factor with $a_k$.Let the sequence be in increasing order,let $a_{i+1}=a_i+d_i$ and then set $j=i+1,gcd(a_{i+1},a_i)=1$ which means $gcd(a_i,d_i)=1\forall i$,thus $d_i=1$.So
$a_{i+1}=a_i+1=a_{i-1}+2=a_1+i=i+1$
$W^5.$