# Find last 3 digits of $2032^{2031^{2030^{\dots^{2^{1}}}}}$

Find the last 3 digits of this number $$2032^{2031^{2030^{\dots^{2^{1}}}}}$$ So obviously we are looking for $$x$$ so that $$2032^{2031^{2030^{\dots^{2^{1}}}}} \equiv x \quad \text{mod}\hspace{0.1cm} 1000$$ I also know that usually you use Euler' theorem here, but that only works when the numbers $$a$$ and $$n$$ are coprime, but $$2032$$ and $$1000$$ are not coprime? I can easily find $$\varphi(1000)$$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?

• The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$ – Mark Bennet Mar 24 at 21:20
• @Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus. – Bill Dubuque Mar 24 at 23:59
• Bah, that's no monster. Graham's Number is a monster! – Cort Ammon Mar 25 at 5:48

$$\bmod 1000\!:\ 32^{\large 2031^{\LARGE 2k}}\!\!\equiv\, 8\left[\dfrac{\color{#0a0}{32^{\large 2031^{\LARGE 2k}}}}8 \bmod \color{#0a0}{125}\right]\! \equiv 8\left[\dfrac{\color{#c00}{32}}8\bmod 125\right]\! \equiv 32,\$$ by

\ \,\begin{align} \!\bmod \color{#0a0}{125}\!:\ \color{#0a0}{32^{\large 2031^{\LARGE 2k}}}\!\! &\equiv\, 2^{\large 5\cdot 2031^{\LARGE 2k}\! \bmod 100}\ \ \ {\rm by\ \ } 100 = \phi(125)\ \ \ \rm [Euler\ totient]\\ &\equiv\,2^{\large 5(\color{#b6f}{2031}^{\LARGE \color{#d4f}2k}\! \bmod 20)}\ \ \ {\rm by\ \ \ mod\ Distributive\ Law}\\ &\equiv\,{2^{\large 5(\color{#b6f}1^{\LARGE k})}}\equiv\, \color{#c00}{32}\ \ \ \ \ \ \ \ \ \ \ {\rm by}\ \ \ \color{#b6f}{2031^{\large 2}}\!\equiv 11^{\large 2}\equiv\color{#b6f} 1\!\!\!\pmod{\!20}\\ \end{align}

• We used twice: $\,\ ab\bmod ac\, =\, a\,(b\bmod c)\, =\,$ mod Distributive Law $\ \$ – Bill Dubuque Mar 24 at 22:50
• How would you prove this? – Markus Punnar Mar 25 at 11:23
• @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment. – Bill Dubuque Mar 25 at 13:05

It's a lot simpler than it looks. I shall call the number $$N$$.

You will know the residue modulo $$10^3$$, thus the last three digits, if you first get the residues modulo $$2^3=8$$ and modulo $$5^3=125$$.

$$N$$ is obviously a multiple of $$8$$, thus $$N\equiv 0\bmod 8$$. Which leaves $$\bmod 125$$.

The base $$2032\equiv 32$$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $$\bmod 100$$ where $$100$$ is the Euler totient of $$125$$. But the exponent on $$2032$$ has the form

$$2031^{10k}=(2030+1)^{10k}=(\text{binomial expansion})=100m+1$$

So $$N\equiv 32^1\equiv 32\bmod 125$$. The only multiple of $$8$$ between $$0$$ and $$999$$ satisfying this result is $$32$$ itself so ... $$N\equiv 32\bmod 1000$$. Meaning the last three digits were there all along, the $$\color{blue}{032}$$ in the base $$2032$$!

• (+1) same answer I got, by means similar enough that I won't add another post here. – robjohn Mar 24 at 22:25
• Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer. – Bill Dubuque Mar 24 at 23:27

Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.

$$2032^{monster}$$ and $$1000$$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.

$$2032^{monster} = 0 \pmod 8$$ and so we just need to solve $$2032^{monster} \pmod {125}$$ and for that we can use Euler Theorem.

$$\phi(125=5^3) = (5-1)*5^{3-1} = 100$$.

So $$2032^{monster} \equiv 32^{monster \% 100}$$.

And $$monster = 2031^{littlemonster}\equiv 31^{littlemonster}\pmod {100}$$

$$31$$ and $$100$$ are relatively prime and $$\phi(100)= 40$$ so

$$31^{littlemonster} \equiv 31^{littlemonster \% 40} \pmod {100}$$.

$$littlemonster = 2030^{smallmonster}$$ but $$5|2030$$ and as $$smallmonster > 2$$ we know $$8|2^{smallmonster}$$ and $$2^{smallmonster}|2030^{smallmonster}$$.

So $$littlemonster \equiv 0 \pmod {40}$$.

$$2031^{littlemonster} \equiv 31^0 \equiv 1 \pmod {100}$$

So $$2032^{monster} \equiv 32 \pmod {125}$$

So $$2032^{monster} \equiv 0 \pmod 8$$ and $$2032^{monster} \equiv 32 \pmod {125}$$.

As $$8|32$$ we are done. $$2032^{monster} \equiv 32 \pmod {1000}$$.

and the last three digits are $$032$$.

• Good idea, but you rendered $2031^{2030^{···}} \bmod 125$. You need $2032^{2031^{2030^{···}}} \bmod 125$. – Oscar Lanzi Mar 25 at 1:30
• oops.............. – fleablood Mar 25 at 11:58
• Actually I rendered it as $2032^{2031^{...}}\equiv 31^{2031^{...}}\pmod{125}$... which is still an error. – fleablood Mar 25 at 12:02

By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $$1000$$, you can split that into 2 problems: Find the remainder$$\mod 8$$ and$$\mod 125$$. Obviously

$$z_0:=2032^{2031^{2030^{\dots^{2^{1}}}}} \equiv 0 \pmod 8$$

What remains to be found is $$x_0 \in [0,124]$$ in

$$z_0 \equiv x_0 \pmod {125}.$$

As $$z_0$$ is now coprime to $$125$$, you can apply Euler's theorem now. With

$$z_1:=2031^{2030^{\dots^{2^{1}}}}$$

and

$$\phi(125)=100$$ the new problem becomes to find $$x_1 \in [0,99]$$ in

$$z_1 \equiv x_1 \pmod {100}$$

and then use

$$32^{x_1} \equiv x_0 \pmod {125}$$

to find $$x_0$$.

So this reduced the original problem$$\mod 1000$$ to a smaller problem$$\mod 100$$.

Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $$\mod 2$$).

Then to solve the original problem you need to back-substitute the calculated $$x_i$$ to get $$x_{i-1}$$, just as outlined for $$x_1,x_0$$ above.