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

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?

• I'm pretty sure there are no "simple" solutions to any problems that appear in the Russian (or other national) Math Olympiads ;-) – PurpleVermont Apr 12 '14 at 20:38
• I know. I rather mean brief. – user140619 Apr 12 '14 at 20:41
• As @chubakueno has pointed out, the claim is false for finite sequences, e.g., $(a_{1},a_2)=(2,1)$ is a counter-example. – mathse Apr 13 '14 at 16:48

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.

• Great. I got it. Also, it seems that my teacher is taking quite a lot of the problems he gives me from that book. Maybe I should buy it. – user140619 Apr 12 '14 at 20:43

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

• I did not understand why $\text{gcd}(j, a_j) = j$. – Anant Apr 13 '14 at 12:17
• Since $a_j=rj$, then $\gcd(j,rj)=j\gcd(1,r)=j$. – mathse Apr 13 '14 at 12:19
• Thanks! I was staring at $j | a_j$, but only now it struck me that is obviously implies $\text{gcd}(j, a_j) = j$. Embarassing :) – Anant Apr 13 '14 at 12:24
• Yes, to offset, you have to upvote my answer :) – mathse Apr 13 '14 at 12:26
• But how is guaranteed that when $a_i=j$, $a_j$ is defined? – chubakueno Apr 13 '14 at 14:46