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.
Here my suggested proof:
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$.