6
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user140619 Apr 12 '14 at 20:43
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I did not understand why $\text{gcd}(j, a_j) = j$. $\endgroup$ – Anant Apr 13 '14 at 12:17
  • 1
    $\begingroup$ Since $a_j=rj$, then $\gcd(j,rj)=j\gcd(1,r)=j$. $\endgroup$ – mathse Apr 13 '14 at 12:19
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Anant Apr 13 '14 at 12:24
  • $\begingroup$ Yes, to offset, you have to upvote my answer :) $\endgroup$ – mathse Apr 13 '14 at 12:26
  • $\begingroup$ But how is guaranteed that when $a_i=j$, $a_j$ is defined? $\endgroup$ – chubakueno Apr 13 '14 at 14:46

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.