Find this sequence $a_{i}$ such $\gcd{(a_{i},a_{j})}=\gcd{(i,j)}$ 
A sequence $a_{1},a_{2},\cdots $ of natural numbers satisfies
  $$\gcd{(a_{i},a_{j})}=\gcd{(i,j)},\textrm{ for all } i\neq j$$
Prove that $$a_{i}=i\quad\textbf{for all } i$$

My approach is the following:
For any integer $m$,we have $$\gcd{(a_{m}.a_{2m})}=\gcd{(2m,m)}=m\Longrightarrow m \mid a_{m}$$
now I'm stuck and don't know how to proceed？
 A: For every $n$ we have 
$$
\gcd(a_{n}, a_{2n}) = \gcd(n, 2n) = n,$$
 so $n \mid a_{n}$. 
If, by way of contradiction, $a_{n} > n$ for some $n$, let $p$ be a prime such that $p n \mid a_{n}$. Then
$$
p n \mid \gcd(a_{n}, a_{p n}) = \gcd(n, p n) = n,
$$
a contradiction.

A variation on the second paragraph. If $n \ne a_{n}$, then
$$
a_{n} \mid \gcd(a_{n}, a_{a_{n}}) = \gcd(n, a_{n}) = n,
$$
so $a_{n} = n$ anyway.
A: Let be $k=\frac{a_m}m$.
Then, let's say that
$$d=\gcd(a_m,a_{k})=\gcd(m,k)$$
but $k\mid a_{k}$ and hence $k\mid d$. Therefore, $k=d$ and $k|m$. We see that $a_m/m$ divides $m$ for every natural $m$.
Let $m=1$ to see that $a_1=1$.
Now let $m=p$, a prime number. Then $a_p/p$ divides $p$, therefore $a_p$ is $p$ or $p^2$. And $a_{p^2}$ is a multiple of $p^2$. But
$$\gcd(a_p,a_{p^2})=\gcd(p,p^2)=p$$
Therefore $a_p=p$.
Similarly, $a_{p^r}/p^r$ divides $p^r$ and hence $a_{p^r}=p^s$ where $r\le s\le 2r$, but
$$\gcd(a_{p^r},a_{p^s})=\gcd(p^r,p^s)=p^r$$
so $a_{p^r}=p^r$.
Now take any natural $n$. For every prime power $p^r$,
$$\gcd(a_n,p^r)=\gcd(a_n,a_{p^r})=\gcd(n,p^r)$$
This implies that $a_n=n$.
A: You already showed that $i\vert a_i$.
So we know, $a_i\vert a_{a_i}$.
From here, just let the following magic happen:
$$i=gcd(i,a_i)=gcd(a_i,a_{a_i})=a_i$$
