Math Olympiads: GCD of terms in a sequence equals GCD of their indices.

Question

The sequence $a_1 ,a_2 ,a_3 ,...$ of positive integers satisfies $\text{gcd}(a_i ,a_j ) = \text{gcd} (i, j)$ for $i \neq j$. Prove that $a_i = i$ for all $i$.

Source: Russian Mathematical Olympiad, 1995.

Are there any simple solutions to this problem that you can suggest?

Answer 1

For any integer $m$, we have $\text{gcd}(a_m, a_{2m}) = \text{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 $\text{gcd}(a_m, a_n) = \text{gcd}(m, n)$. Thus $a_n$ has exactly the same divisors as $n$. Hence it must equal $n$, for all $n$.

References:

R. Gelca and T. Andreescu, Putnam and Beyond, Springer, 2007.

Answer 2

Let $a_i=j$. Then, $i=\gcd(i,2i)=\gcd(a_i,a_{2i})=\gcd(j,a_{2i})$, so $i|j$, i.e. $i|a_i$, for all $i$.

Again, let $a_i=j$; from above $i|j$. But also $\gcd(i,j)=\gcd(a_i,a_j)=\gcd(j,a_j)=j$, so $j|i$. Hence, $i=j=a_i$ for all $i$.

Actually the last line can be shortened to: Again, let $a_i=j$. Then, $i=\gcd(i,a_i)=\gcd(i,j)=\gcd(a_i,a_j)=\gcd(j,a_j)=j$.