How to prove that for every $i$, $a_i = i$

Question

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$?

Answer 1

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.

Answer 2

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$