Hcfyk

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?

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

$ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{large 2031^{LARGE 2k}}}!!
&equiv, 2^{large 5cdot 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}equivcolor{#b6f} 1!!!pmod{!20}\
end{align} $

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 $Nequiv 0bmod 8$. Which leaves $bmod 125$.

The base $2032equiv 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 $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $color{blue}{032}$ in the base $2032$!

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

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.