How to prove that for every $i$, $a_i = i$ I am a beginner in number theory and I would like some hints to solve the following  problem :
Assume we have natural numbers $a_1,a_2,...$ such that $i$ is not equal to $j$ and $\gcd(a_i , a_j) = \gcd(i,j)$. Prove that $a_i = i$.
I know that I have to show $i$ counts $a_i$ and $a_i$ counts $i$ but I don’t know how to show this.
Since $\gcd(i,j) = \gcd(j,i)$ is it also true that $a_i = j$?
 A: First, note that $a_i=i$ works.
Next, note that $i|a_i$ because $\gcd(a_i,a_{2i})=\gcd(i,2i)=i$
Now assume that for some $a_i,$ there is $k \gt 1$ such that $ a_i=ik$.  We know that $ik|a_{ik}$, so  $ik|\gcd(a_i,a_{ik})\neq \gcd(i,ik)$ is a contradiction, so there is no such $i$.  
This fails if your sequence is not infinite.  If there are only $n$ terms in your sequence, you could multiply each term in the sequence by a different prime greater than $n$ and get a new sequence that worked.
A: Hint $ $ [migrated from a deleted thread]
$$\begin{align}\rm n\:\!\neq\, {\small 2}\:\!n\ \Rightarrow\  &\rm ({An},A\:\!{{\small 2}\:\!n}) =\:\! (n,\:\!2\:\!n)\:\!\Rightarrow \ \ \ \color{#c00}{n\mid{An}}\\[.3em]
 \rm n\neq An\ \Rightarrow\  &\rm \underbrace{(An,AAn)}_{\Large\color{#c00}{An}}\! = (n,An)\Rightarrow An\mid n\,\Rightarrow\, n = An  \end{align}\qquad$$
Alternatively using the gcd universal property $\ d\mid a,b\iff d\mid(a,b)\ $ we have
$$\begin{align} m\mid a_n &\iff m\mid\ a_m,\ a_n\ \ \ \ \, {\rm by}\ \ m\mid a_m\\
&\iff m\mid (a_m,a_m)\ \ \ \rm by\ \  gcd\ universal\ property\\
&\iff m\mid (m,n)\ \ \ \ \ \ \ {\rm by\ hypothesis, and}\ \ m\neq n\\
&\iff m\mid \, \ m,n \ \ \ \ \ \ \ \ \,\rm by\ \  gcd\ universal\ property\\
&\iff m\mid n 
\end{align}$$
So $a_n$ and $n$ have the same set $S$ of divisors $m$, so the same $\rm\color{#c00}{greatest}$ divisor $\, a_n = \color{#c00}{\max} S = n$
