Demostrar que $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 9 = 7$

Question

Demostrar que $\underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{2016 \mbox{ times}} \mod 9 = 7$

Creo que se puede hacer por inducción:

Base:
$2^{2^{2^{2}}} \equiv 2^{16} \equiv 2^8 \cdot 2^8 \equiv 2^4 \cdot 2^4 \cdot2^4 \cdot2^4 \equiv 7^2 \cdot 7^2 \equiv 4 \cdot 4 \equiv 16 \equiv 7$

Supongamos que es cierto para $n$ tiempos.
Dejemos que $a_n = \underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{n \mbox{ times}}$ $$ a_{n+1} = 2^{a_n} = 2^{9k+7} = 2^7 \cdot 2^{9k} \equiv 128 \cdot 1 \equiv 2 \neq 7 $$ ¿En qué me he equivocado?

Answer 1

Sólo porque estamos trabajando en módulo $9$ Eso no significa que el exponentes trabajar en módulo $9$ . En general, $2^{9k}\not\equiv 1$ . En realidad, si $k$ es impar, $2^{9k}\equiv -1$ . Que es exactamente lo que falla aquí: Usted está recibiendo $-7\equiv 2$ en lugar de $7$ .

Por supuesto, puedes intentar tener esto en cuenta en tu prueba de inducción. Pero te encuentras con el problema de tratar de seguir la pista de pares e Impares módulo $9$ , lo que significa que básicamente has subido al módulo $18$ Y si tenemos mala suerte (no creo que la tengamos en este caso), esto explotará.

Tenemos $2^6 = 64\equiv 1$ Así que mirando el exponente modulo $6$ parece que sería más natural que modulo $9$ .

Para ayudar a mantener las cosas claras, presentaré los colores de nuestra "torre de energía": $$ 2^{\displaystyle\color{red}2^{\displaystyle\color{blue}2^{\displaystyle\color{orange}2^{\cdot^{\cdot^2}}}}} $$ donde la base es negra, el primer exponente es rojo, el seoncd es azul, el tercero es naranja, y después resulta que podemos dejar de preocuparnos.

Ahora, mirando el número rojo modulo $6$ tenemos $\color{red}2^\color{blue}{3} \equiv \color{red}2^\color{blue}{1}$ y $\color{red}2^\color{blue}{4}\equiv \color{red}2^\color{blue}{2}$ , por lo que al mirar el número azul módulo $2$ parece que podría ser útil (siempre y cuando nos aseguremos de que es estrictamente positivo).

Y vemos que el número azul es estrictamente positivo y par (es un $2$ elevado al número naranja, y el número naranja es estrictamente positivo). Así que también puede ser un $2$ en lo que respecta al número rojo. Lo que significa que el número rojo bien podría ser un $4$ en lo que respecta al número negro. Así, terminamos con $2^\color{red}4\equiv 7$ modulo $9$ para nuestra respuesta final.

Trabajando de esta manera, por cada nivel que se suba en la torre de exponentes, el módulo que nos interesa bajará. Finalmente, en algún momento (normalmente bastante rápido), básicamente sólo nos interesa si el resultado de la torre restante es par o impar (y posiblemente si es mayor que algún número relativamente pequeño), y entonces podemos volver a bajar.

Answer 2

Donde fallas, es en asumir que los exponentes mod el módulo funciona. Generalmente no lo haría. El exponente es mod 6, cuando se hace mod 9. Así que lo obtienes equivalente a: $$128\cdot 2^{3k}=128\cdot8^k$$ Que luego depende de la paridad de k (porque el orden de 8 mod 9 es 2).

Answer 3

Para el correcto forma de hacer la reducción de exponente modular ver aquí . Utilizando ese método

$\!\!\bmod 9\!:\,\ 2^{\Large\color{#c00} 6}\equiv 1\ \ {\rm thus}\ \ 2^{\large N}\equiv\, 2^{\large N\Large \bmod\, \color{#c00}6}\ $

$\text{Applying that here}\!:\ 2^{\Large {2^{\Large 2K}}}\!\!\equiv\, 2^{\Large \color{#0a0}{2^{\Large 2K}}\!\bmod\color{#c00} 6}\!\equiv 2^{\Large\color{#0a0} 4}\equiv 7$

$\text{since we have that:}$ $\bmod \color{#c00}6\!:\,\ \color{#0a0}{2^{\large 2K}}\!\equiv 4^{\large K}\!\equiv\color{#0a0} 4,\,$ por $\,4^{\large 2}\equiv 4\,$ y la inducción (o por aquí ).