I was reading the book Putnam and Beyond. When I tried to calculate some examples, I came across one that I did not calculate, so I looked at the solution, but I did not understand it.
Here is the task:
The sequence $a_1,\,a_2,\,a_3,\,…$ of positive integers satisfies $\gcd(a_m,a_n)=\gcd(m,n)$ for $m\neq n$. Prove that $a_n=n$ for all $n$.
Here is the solution:
For any integer $m$, we have $\gcd(a_m,a_{2m})=\gcd(2m,m)=m$, and so $m$ divides $a_m$. Then, it follows that for any other integer $n$, $m$ divides $a_n$ if and only if it divides $\gcd(a_m,a_n)=\gcd(m,n)$. Thus $a_n$ has exactly the same divisors as $n$. Hence it must equal $n$, for all $n$.
More specifically, I did not understand the second and third sentences.
Thank you in advance.
Best Answer
Once you have that $m|a_m$, another way to argue is
Assume there is $a_n$ with $a_n \neq n$. Then $a_n=kn$ for some $k \gt 1$. We also know $kn|a_{kn}$, which would give $\gcd(a_n,a_{kn})=kn \neq n$ as required so we have a contradiction.