En el GCD de dos palíndromos.

Question

Tuve una observación. Lo cual discutiré a continuación. Mi pregunta será ¿Es correcta mi observación? Si es así, ¿cómo puede uno probarlo?

Observación:

Considere la cadena de palíndromos a continuación:

$100...01$ y$111...11$

Observé que:

$gcd(100...01,111...11)=1$ si la longitud de la cadena es impar mientras

$gcd(100...01,111...11)=11$ si la longitud de la cadena es par.

Muchas gracias por la gran ayuda.

Answer 1

Lo que voy a hacer a continuación es el llamado algoritmo de Euclides. Si usted no está familiarizado con ella, yo te puedo mostrar algunas de las explicaciones de que en las otras preguntas/sitios Web, si usted me pregunta en los comentarios.

Tenemos: $$\text{gcd}\left(10^k+1, \sum_{i=0}^k 10^k\right)$$ El segundo elemento es más grande, por lo que resta del primer elemento: $$\text{gcd}\left(10^k+1, \sum_{i=1}^{k-1} 10^k\right)$$ Observe cómo el segundo elemento ya no tiene lugar o $10^k$ lugar. Ahora, el primer elemento es más grande, por lo que resta del segundo elemento, que afecta a todos los dígitos del primer elemento, excepto el primero y el último: $$\text{gcd}\left(91+\sum_{i=2}^{k-1} 8\cdot 10^k, \sum_{i=1}^{k-1} 10^k\right)$$ Observe cómo he cambiado la suma del índice de $i=1$ $i=2$y trajo el lugar de las decenas en hacer $91$ frente. Ahora, ¿esto $8$ más de veces, deshacerse de la suma y resta de $91$ $80$ lo que nos da $11$: $$\text{gcd}\left(11, \sum_{i=1}^{k-1} 10^k\right)$$

Ahora, $11$ es primo por lo que el MCD es $1$ o $11$:

• Si $k$ es par, entonces tenemos un número impar de $1$s en el segundo elemento y no es divisible por $11$, por lo que el MCD es $1$.
• Si $k$ es impar, entonces tenemos un número par de $1$s en el segundo elemento, y es divisible por $11$, por lo que el MCD es $11$.

Por lo tanto, desde que me lo acaba de probar una reafirmación de su observación, su observación era de hecho correcta. Buen trabajo!