Math Olympiads: GCD of terms in a sequence equals GCD of terms in other sequence

Recently, someone asked for a proof of a problem from the Russian Mathematical Olympiad, 1995. Math Olympiads: GCD of terms in a sequence equals GCD of their indices.

The problem was to show that if the terms in an infinite sequence $a_1,a_2,a_3,\ldots$ satisfy $\gcd(a_i,a_j)=\gcd(i,j)$ for all $i\neq j$, then $a_i=i$ for all $i$.

@Anant suggested to generalize this, e.g., in the following way:

Conjecture: Let $a_1,a_2,a_3,\ldots$ and $b_1,b_2,b_3,\ldots$ be two infinite sequences such that $a_i,b_i\in\mathbb{N}$, where $\mathbb{N}$ is the set of positive integers. Assume that $\gcd(a_i,a_j)=\gcd(b_i,b_j)$ for all $i\neq j$. Then $a_i=b_i$ for all $i$.

I think this is an interesting problem, so I ask it here. However, this conjecture is false, as the counterexample $a_i=1$ for all $i$, $b_i=i^{\text{th}}$ prime shows. Still, I think the conjecture holds true when we additionally require that $B=\{b_i|i\ge 0\}=\mathbb{N}$.

I think I have a proof, but am a bit uncertain, so I maybe wait a bit to see if someone finds a counterexample or gives a rigorous proof. If no proof or disproof pops up, I'll post mine.

• For each $k\in\mathbb{N}$ let $n_k$be the multi-valued function that returns all indexes for which $b_{n_k}=k$. Now replace in the same proof as before each subindex $k$ by $n_k$. We get that $a_{n_k}$ has exactly the same divisors as $b_{n_k}$. – user141763 Apr 13 '14 at 21:51
• @Richard Why does this fail when $B\subsetneq \mathbb{N}$? Also, for example, in the counterexample $b_3=5$ but $a_3=1$ ... Or do I not understand your proof? – mathse Apr 13 '14 at 22:16
• It fails because there are sequences of finite length, most importantly finite A or B, which are counterexamples. There are also sequences where A and B are infinite, but not N, which do not satisfy the conditions of the problem. – Calvin Lin Apr 13 '14 at 22:32
• @CalvinLin Well I'm asking for a proof of the yet unproven claim. This claim I made up, so to speak. We have to verify it - I have my concerns with Richard's answer. (finite sequences clearly fail, we only consider infinite sequences) – mathse Apr 13 '14 at 22:36
• The reason why it works for $\mathbb{N}$ but not for smaller sets is because the statement "If (for all $d\in A$, $d|a$ iff $d|b$) then $a=b$" is true when $A$ contains all possible divisors (i.e. $A=\mathbb{N}$). – user141763 Apr 13 '14 at 23:58

Choose $b_i$ arbitrary. Since $B=\mathbb{N}$, there exists $b_j$ such that $b_j=2b_i$. Then $b_i=\gcd(b_i,b_j)=\gcd(a_i,a_j)$. Hence $b_i|a_i$ for all $i$.
Therefore, all $a_i$ are of the form $a_i=\beta_ib_i$. Assume there exists $a_i=\beta_ib_i$ with $\beta_i>1$. We have \begin{align*} \gcd(b_i,b_j)=\gcd(a_i,a_j) = \gcd(\beta_ib_i,\beta_jb_j) \end{align*} for all $b_j$ such that $j\neq i$. Since $B=\mathbb{N}$, there exists $b_k$ such that $b_k=a_i=\beta_ib_i$. Thus, for this element, \begin{align*} b_i=\gcd(b_i,\beta_ib_i)=\gcd(b_i,b_k)=\gcd(a_i,a_k)=\gcd(\beta_ib_i,\beta_kb_k) = \gcd(\beta_i b_i,\beta_k\beta_ib_i)= \beta_ib_i, \end{align*} which is a contradiction since $\beta_i>1$. Therefore, all $\beta_i=1$, and, as required, $a_i=b_i$.