Matemáticas Olimpiadas: MCD de los términos de una secuencia es igual a MCD de los términos en otra secuencia

Question

Recientemente, alguien le preguntó por una prueba de un problema de la federación Olimpiada Matemática, 1995. Matemáticas Olimpiadas: MCD de los términos de una secuencia es igual a MCD de sus índices.

El problema era mostrar que si los términos de una secuencia infinita $a_1,a_2,a_3,\ldots$ satisfacer $\gcd(a_i,a_j)=\gcd(i,j)$ todos los $i\neq j$, $a_i=i$ todos los $i$.

@Anant sugerido para generalizar este, por ejemplo, de la siguiente manera:

Conjetura: Vamos a $a_1,a_2,a_3,\ldots$ $b_1,b_2,b_3,\ldots$ dos infinito secuencias que $a_i,b_i\in\mathbb{N}$ donde $\mathbb{N}$ es la conjunto de enteros positivos. Suponga que $\gcd(a_i,a_j)=\gcd(b_i,b_j)$ todos los $i\neq j$. A continuación, $a_i=b_i$ todos los $i$.

Creo que este es un problema interesante, así que lo pregunto aquí. Sin embargo, esta conjetura es falsa, como el contraejemplo $a_i=1$ para todos los $i$, $b_i=i^{\text{th}}$ primer muestra. Aún así, yo creo que la conjetura es verdadera cuando nos adicionalmente requieren que $B=\{b_i|i\ge 0\}=\mathbb{N}$.

Creo que tengo una prueba, pero estoy un poco incierto, así que tal vez esperar un poco a ver si alguien encuentra un contraejemplo o da una rigurosa prueba. Si no hay prueba o refutación aparece, voy a publicar el mío.

Answer 1

Aquí mi sugerencia de prueba:

Elija $b_i$ arbitrarias. Desde $B=\mathbb{N}$ existe $b_j$ tal que $b_j=2b_i$. A continuación,$b_i=\gcd(b_i,b_j)=\gcd(a_i,a_j)$. Por lo tanto $b_i|a_i$ todos los $i$.

Por lo tanto, todos los $a_i$ son de la forma $a_i=\beta_ib_i$. Asumir que hay existe $a_i=\beta_ib_i$$\beta_i>1$. Tenemos \begin{align*} \gcd(b_i,b_j)=\gcd(a_i,a_j) = \gcd(\beta_ib_i,\beta_jb_j) \end{align*} para todos los $b_j$ tal que $j\neq i$. Desde $B=\mathbb{N}$ existe $b_k$ tal que $b_k=a_i=\beta_ib_i$. Por lo tanto, para este elemento, \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*} lo cual es una contradicción ya que el $\beta_i>1$. Por lo tanto, todos los $\beta_i=1$, y, según sea necesario, $a_i=b_i$.