Crthuky

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

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=(textbinomial 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 $colorblue032$ in the base $2032$!

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.

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^littlemonsterequiv 31^littlemonsterpmod 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 31 pmod 125$

So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.

So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.

I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and

$2032^monster equiv 656pmod1000$

$bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by

$ ,beginalign !bmod color#0a0125!: color#0a032^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#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
&equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
endalign $