Last 3 digits of $3^{3^{3^3}}$

Question

I am trying to find the last $3$ digits of $\,3^{\large 3^{3^3}}$, i.e. $\,3^{\large 3^{3^3}}\! \bmod 1000$.

My idea is to apply Euler's totient function in some way, but I am unsure on how to proceed. Would someone be able to help me out?

Answer 1

The prior $2$ answers omit hard calculations (too difficult mentally). Below is an easy way to do it purely mentally. Nothing is omitted. We use only $\rm B :=$ Binomial theorem and modular arithmetic.

$\!\!\bmod 200\!:\ \ \ \color{#c00}{3^{\large 20}}\equiv\, 1\,\ $ by $\,\ 9^{\large 10}\equiv\, (-1 + 10)^{\large 10}\overset{\rm B}\equiv 1 - {10}\cdot 10 + 5\cdot 9\cdot 10^{\large 2} \equiv 4401\equiv 1,\,$ so

$\!\! \bmod 1000\!:\ 3^{\large 100}\!\equiv 1\, $ by $\, ( \color{#c00}{3^{\large 20}})^{\large 5}\equiv (1\!+\!200k)^{\large 5}\overset{\rm B}\equiv 1 + 5\cdot 200k\equiv 1,\,$ therefore

$ 3^{\large 3^{\large 3^{\Large 3}}}\!\!\!\equiv 3^{\large \color{#0a0}{3^{\large 3^{\Large 3}}}\!\bmod{{100}}}\!\equiv 3^{\large\color{#0a0}{87}}\!\equiv 3(\color{#e94}{3^{\large 86}})\equiv 3(129)\equiv 387\ $ by below:

$\ \ \ \bmod 100\!:\ \ \smash[t]{\color{#0a0}{3^{\large 3^{\LARGE 3}}}}\!\equiv\, \color{#0a0}{87}\,$ by $\, \color{#c00}{3^{\large 27}}\!\equiv 3^{\large 7}\!\equiv 3^{\large 3} 3^{\large 4}\equiv 27(1\!-\!20)\equiv 27\!-\!40,\ $ and

$\ \bmod 1000\!:\ \color{#e94}{3^{\large 86}}\!\equiv 129\,$ by $\, 9^{\large 43}\!\equiv (-1\!+\!10)^{\large 43}\overset{\rm B}\equiv -1\! +\! 43(10)\!-\!\underbrace{43(21)}_{\large \color{#d4f}3+10j}10^{\large 2}\!\equiv -1\!+\!430\!-\! \color{#d4f}300$

Answer 2

Hints:

First you should use the Chinese remainder theorem, i.e. determine the values $a$ and $b$ of $\;3^{3^{3^3}}$ modulo $8$ and $125$, then deduce its value modulo $1000$, with the formula deduced from a Bézout's identity between $8$ and $125$: $$47\cdot 8-3\cdot 125=1$$ (found, e.g. by the extended Euclidean algorithm) $$3^{3^{3^3}}\equiv b\cdot 47\cdot 8-a\cdot 3\cdot 125\mod 8\cdot125.$$

Now $a$ is easy to find since $3$ has order $2\bmod8$, so even powers of $3$ are congruent to $1$, odd powers congruent to $3$. Modulo $125$, it requires a little more work: as $\varphi(125)=100$, and $3$ is coprime to $125$, one has, by Euler's theorem, $$3^{3^{3^3}}\equiv 3^{3^{3^3}\bmod100},$$ therefore we have to compute the values of $\;3^{3^3}=3^{27}\bmod100$, which can be done by the fast exponentiation algorithm (‘square and divide’). Here is a layout. The last column contains the successive powers $P$ of $x$ (initially, $P=1$), until the exponent $n=27$ is attained \begin{array}{rcll} n&& \text{squaring}\;& P\\ \hline 27&& x & x \\ 13 && x^2 & x^2\cdot x=x^3 \\ 6 && x^4 & x^3 \\ 3 && x^8 & x^8\cdot x^3 = x^{11} \\ 1 && x^{16} & x^{16}\cdot x^{11}=x^{27}\\ \hline \end{array} You'll find $\;3^{3^3}\equiv 87\mod 100$. There remains to compute $\;3^{87}\bmod 125$, which can be done again with the fast exponentiation algorithm ($6$ squarings and $4$ multiplications mod. $125$).

It can be made a little faster using that $a^{87}\equiv a^{-13}=(a^{-1})^{13}\mod 125$. . As $3^{-1}\equiv 42\mod 125$, this amounts to $\;42^{13}\bmod 125$ ($3$ squarings, $2$ multiplications).