Últimos dígitos de una potencia de 2

Question

Demuestra que existe una potencia de 2 tal que los últimos 1000 dígitos de su representación decimal son todos 1 y 2.

Un hecho que creo que se puede utilizar en este problema: si $2^{n}=\cdots dn$ donde $d$ es el dígito a la izquierda de $n$ entonces $2^{dn}=\cdots dn$ (Un concepto que se utilizó en MMO 1978).

Además, tengo la sensación de que reducir $n$ a su base binaria o ternaria puede ser de ayuda.

Si uno considera que la pregunta es errónea, por favor, mencione por qué esto nunca es posible.

Gracias.

Answer 1

Dejemos que $n = 1000$ . Desde $\Bbb Z/10^n \Bbb Z = (\Bbb Z/2^n \Bbb Z)\times(\Bbb Z/5^n \Bbb Z)$ un primer paso es indagar sobre los posibles valores de las potencias de $2$ modulo $2^n$ y $5^n$ .

La primera es fácil: Si $k\ge n$ entonces $2^k \equiv 0 \pmod {2^n}$ . Y con suficiente suerte, podemos encontrar una solución con $k \ge 1000$ así que no pensemos en $k<1000$ por ahora.

En cuanto a la segunda, se puede demostrar que el orden de $2$ es $4.5^{n-1}$ en el grupo multiplicativo $(\Bbb Z/5^n \Bbb Z)^*$ y así $2$ genera ese grupo :
En primer lugar, comprobamos que $2$ es de orden $4$ modulo $5$ y que $2^4 = 3.5 + 1 \neq 1 \pmod {5^2}$ . Desde $(2^4)^5 \equiv 3.5^2 + 1 \pmod {5^3} \equiv 1 \pmod {5^2}$ , $2$ es de orden $20$ modulo $5^2$ . Y así sucesivamente, $(2^4)^{5^k} \equiv 3.5^{k+1} + 1 \pmod {5^{k+2}} \equiv 1 \pmod 5^{k+1}$ Por lo tanto $2$ es de orden $4.5^k$ modulo $5^{k+1}$ .
Esto demuestra que los poderes de $2$ modulo $5^n$ son exactamente las clases invertibles módulo $5^n$ es decir, los que no son divisibles por $5$ .

Por último, tenemos que demostrar que existe una clase módulo $10^n$ que contiene sólo los dígitos $1$ y $2$ tal que no sea divisible por $5$ (¡fácil!), y es divisible por $2^n$

De hecho, podemos demostrar que para todos los $x \in \Bbb Z/2^n \Bbb Z$ hay un único $y \in \Bbb Z/10^n \Bbb Z$ tal que $y$ sólo utiliza los dígitos $1$ y $2$ y $y \equiv x \pmod {2^n}$ :
Esto es cierto para $n=1$ , si $x=1 \pmod {2}$ elegimos $y=1 \pmod {10}$ y si $x=0 \pmod {2}$ elegimos $y=2 \pmod {10}$ . Supongamos que $n>1$ y que $x' \in \Bbb Z/2^{n-1}\Bbb Z$ . Usando la hipótesis de inducción tenemos un único $y' \in \Bbb Z/10^{n-1}\Bbb Z$ tal que $y' \equiv x' \pmod {2^{n-1}}$ . Por encima de $y'$ hay dos clases permitidas mod $10^n$ , $1y$ y $2y$ . Como su diferencia es $10^{n-1} \equiv 2^{n-1} \pmod 2^n$ son distintos y dan modulo $2^n$ las dos clases anteriores $x'$

Aplicando esta prueba obtenemos un número $...1212122112$ con $1000$ dígitos que es divisible por $2^{1000}$ modulo $10^{1000}$ , no divisible por $5$ y por lo tanto es una potencia de $2$ modulo $10^{1000}$ .