5
$\begingroup$

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...

$\endgroup$
  • 5
    $\begingroup$ use the second idea $\endgroup$ – Will Jagy Sep 21 '15 at 18:33
  • $\begingroup$ Could be useful to note $67^2 \cong 67^{26}$. $\endgroup$ – Eric Towers Sep 22 '15 at 4:31
  • 2
    $\begingroup$ finding a^b^c^… mod m $\endgroup$ – phuclv Sep 22 '15 at 6:00
18
$\begingroup$

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*}

$\endgroup$
7
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.