7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – Mark Bennet Mar 24 at 21:20
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Mar 24 at 23:59
  • $\begingroup$ Bah, that's no monster. Graham's Number is a monster! $\endgroup$ – Cort Ammon Mar 25 at 5:48
6
$\begingroup$

$\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} $

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

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

$\endgroup$
  • 2
    $\begingroup$ (+1) same answer I got, by means similar enough that I won't add another post here. $\endgroup$ – robjohn Mar 24 at 22:25
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 24 at 23:27
4
$\begingroup$

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

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

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.

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