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.

  • $\begingroup$ 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}$. $\endgroup$ – user141763 Apr 13 '14 at 21:51
  • $\begingroup$ @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? $\endgroup$ – mathse Apr 13 '14 at 22:16
  • $\begingroup$ 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. $\endgroup$ – Calvin Lin Apr 13 '14 at 22:32
  • $\begingroup$ @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) $\endgroup$ – mathse Apr 13 '14 at 22:36
  • $\begingroup$ 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}$). $\endgroup$ – user141763 Apr 13 '14 at 23:58

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


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.