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

  • $\begingroup$ "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... $\endgroup$
    – JMoravitz
    Sep 27, 2019 at 18:36
  • $\begingroup$ 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 ? $\endgroup$
    – Pegi
    Sep 27, 2019 at 18:41
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Sep 27, 2019 at 18:45

2 Answers 2


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.