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

• "Based on the question I think it is also possible to say $a_i=j$" What is $j$ from $a_i$'s perspective? $a_i$ knows nothing about $j$. For instance, $\gcd(a_6,a_3)=\gcd(6,3)$ as well as $\gcd(a_6,a_8)=\gcd(6,8)$. So, are you suggesting that $a_6 = 3$ is a possibility? Or that $a_6 = 8$? It can't simultaneously be both... Sep 27, 2019 at 18:36
• It should not be a possibility(as you also pointed out), I am saying I don’t know how the proof goes but as in gcd the order of elements does not matter (gcd(i,j) = gcd(j,i)) any proof we have for i would be true for j as well right ?
– Pegi
Sep 27, 2019 at 18:41
• Certainly not... We begin with "suppose that $n$ is a natural number. We wish to prove that $a_n=n$. To accomplish this consider... yada yada... since $\gcd(a_n,a_x)=\gcd(n,x)$ we know that... yada yada... also since $\gcd(a_n,a_y)=\gcd(n,y)$ we also know that..." Here, we can clearly keep track of which of the numbers was $n$ and won't confuse it with $x$ or $y$ since $n$ was the only one that appeared in both equations. Sep 27, 2019 at 18:45

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.

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