How to calculate really big number mod 990

Question

How to calculate $67^{26^{42^{23}}}\mod 990$?

My idea is to solve $x \equiv 42^{23}\mod 990$ then solve $26^x\mod 990$ and so on. But how to "compute" $42^{23}\mod 990$ only with a pencil and a sheet of paper?

Second idea is that we may factor $990$ into $2 \cdot 3^2 \cdot 5 \cdot 11$ and use chinese remainder theorem...

Answer 1

If you don't mind a bit of pen and paper work, you can solve this problem just using a little modular arithmetic.

First, calculate $67^n \mbox{ mod } 990$ for a few $n$. There's no need to calculate each $67^n$ explicitly; just take $67^{n-1} \mbox{ mod } 990$, multiply that by 67, and mod out by 990 again. You'll notice that \begin{equation*} 67^6 \equiv 199 \mbox{ mod } 990 \end{equation*} and thus \begin{equation*} 67^{12} \equiv 1 \mbox{ mod } 990. \end{equation*} Great! Since $67^{n+12} \equiv 67^n \mbox{ mod } 990$ in general, we only need to know $26^{42^{23}} \mbox{ mod } 12$. A bit more hand calculation shows that, for $n \geq 2$, \begin{equation*} 26^{\mbox{ even } n} \equiv 4 \mbox{ mod } 12 \end{equation*} and \begin{equation*} 26^{\mbox{ odd } n} \equiv 8 \mbox{ mod } 12. \end{equation*} Since $42^{23}$ is even, we thus see that \begin{equation*} 26^{42^{23}} \equiv 4 \mbox{ mod } 12. \end{equation*} Therefore \begin{equation*} 67^{26^{42^{23}}} \equiv 67^4 \equiv 661 \mbox{ mod } 990. \end{equation*}

Answer 2

First use the Chinese remainder theorem: $$\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. $$ Now

• $67\equiv1 \mod 2$,
• $67\equiv2 \mod 5$, hence it has order $4$ modulo $5$,
• $67\equiv4 \mod 9$, hence it has order $3$ modulo $9$
• $67\equiv1 \mod 11$.

The order of $67$ modulo $990$ is the l.c.m. of its orders modulo $\;2,5,9$ and $11$: $\;\color{red}{12}$, and $$67^{26^{42^{23}}}\mod 990=67^{26^{42^{23}}\bmod12}$$

Value of the exponent modulo 12: First observe $26\equiv 2\mod 12$; it is easy to check that, if $n\ge 2$, $$2^n\equiv\begin{cases} 4\mod 12&\text{if $n$ is even,}\\8\mod 12&\text{if $n$ is odd.} \end{cases}$$ We conclude that $26^{42^{23}}\equiv2^{42^{23}}\equiv 4 \mod 12$, and $$67^{26^{42^{23}}}\equiv 67^4\equiv 661\mod 990.$$