Cómo calcular el número realmente grande mod 990

Question

Como calcular $67^{26^{42^{23}}}\mod 990$?

Mi idea es resolver$x \equiv 42^{23}\mod 990$ y luego resolver$26^x\mod 990$ y así sucesivamente. Pero, ¿cómo "calcular"$42^{23}\mod 990$ sólo con un lápiz y una hoja de papel?

La segunda idea es que podremos factor$990$ en$2 \cdot 3^2 \cdot 5 \cdot 11$ y usar el teorema del resto chino ...

Answer 1

Si no te importa un poco de la pluma y el papel, este problema se puede solucionar simplemente con un poco de aritmética modular.

En primer lugar, calcular el $67^n \mbox{ mod } 990$ para un par de $n$. No hay necesidad de calcular cada una de las $67^n$ explícitamente; tomemos $67^{n-1} \mbox{ mod } 990$, que se multiplican por el 67, y el mod por 990 de nuevo. Te darás cuenta de que la \begin{equation*} 67^6 \equiv 199 \mbox{ mod } 990 \end{ecuación*} y así \begin{equation*} 67^{12} \equiv 1 \mbox{ mod } 990. \end{ecuación*} Genial!!! Desde $67^{n+12} \equiv 67^n \mbox{ mod } 990$ en general, sólo necesitamos saber de $26^{42^{23}} \mbox{ mod } 12$. Un poco más de la mano de cálculo muestra que, para $n \geq 2$, \begin{equation*} 26^{\mbox{ even } n} \equiv 4 \mbox{ mod } 12 \end{ecuación*} y \begin{equation*} 26^{\mbox{ odd } n} \equiv 8 \mbox{ mod } 12. \end{ecuación*} Desde $42^{23}$ es aún, así vemos que \begin{equation*} 26^{42^{23}} \equiv 4 \mbox{ mod } 12. \end{ecuación*} Por lo tanto,\begin{equation*} 67^{26^{42^{23}}} \equiv 67^4 \equiv 661 \mbox{ mod } 990. \end {ecuación*}

Answer 2

Primero utilice el teorema del resto Chino: $$\mathbf Z/990\mathbf Z\simeq \mathbf Z/2\mathbf Z\times\mathbf Z/5\mathbf Z\times\mathbf Z/9\mathbf Z\times\mathbf Z/11\mathbf Z. $$ Ahora

• $67\equiv1 \mod 2$,
• $67\equiv2 \mod 5$, por lo que ha pedido a $4$ modulo $5$,
• $67\equiv4 \mod 9$, por lo que ha pedido a $3$ modulo $9$
• $67\equiv1 \mod 11$.

El orden de $67$ modulo $990$ es el l.c.m. de sus órdenes modulo $\;2,5,9$ y $11$: $\;\color{red}{12}$, y $$67^{26^{42^{23}}}\mod 990=67^{26^{42^{23}}\bmod12}$$

El valor del exponente modulo 12: Primero observamos $26\equiv 2\mod 12$; es fácil comprobar que, si $n\ge 2$, $$2^n\equiv\begin{cases} 4\mod 12&\text{if $n$ is even,}\\8\mod 12&\text{if $$ n es impar.} \end{casos}$$ Llegamos a la conclusión de que $26^{42^{23}}\equiv2^{42^{23}}\equiv 4 \mod 12$, y $$67^{26^{42^{23}}}\equiv 67^4\equiv 661\mod 990.$$