0
$\begingroup$

This problem is originally from PuMAC$^{a}$ $2007$. I tried using modular arithmetic (Euler's totient function$(\phi)$) but could not solve more than this:

I calculated Euler's totient functions separately by the formula $\phi(n)=n\big(1-\frac{1}{p_1}\big)\big(1-\frac{1}{p_2}\big)\cdots\big(1-\frac{1}{p_k}\big),$ and then I worked them with $\pmod{1000}.$ But it looks very tedious!

I used the property that when $a$ and $n$ are relatively prime we have

$a^b\equiv a^{b\mod{\phi(n)}}$ $\mod{n}$

It then suffices to calculate $b\mod{\phi(n)}$.

After this I have not been able to proceed further so I am hoping for someone's help at the moment. Any guidance would be highly appreciated. Thank you!

$\endgroup$
6
  • $\begingroup$ These power towers tend to stabilize pretty quickly. Only the first few lower levels matter; the rest doesn't. $\endgroup$
    – Ivan Neretin
    Commented May 16 at 11:08
  • $\begingroup$ Can you give the solution, I'm dying for it. $\endgroup$
    – NOT ACID
    Commented May 16 at 11:21
  • $\begingroup$ I can't. Rules are rules. $\endgroup$
    – Ivan Neretin
    Commented May 16 at 11:22
  • $\begingroup$ Please see this article on MathSE protocol. $\endgroup$
    – user2661923
    Commented May 16 at 12:13
  • $\begingroup$ FYI, I found the duplicate by looking through the list of linked questions of Modular exponentiation by hand ($a^b\bmod c$). $\endgroup$
    – John Omielan
    Commented May 16 at 15:12

2 Answers 2

Reset to default
1
$\begingroup$

Hint: Use CRT. Let $N$ be the given number then $N\ \mathrm{mod}\ 8$ and $N\ \mathrm{mod}\ 125$ determine $N\ \mathrm{mod}\ 1000$. In your case, $N\ \mathrm{mod}\ 8$ is just $0$ and for modulo $125$, you want to look at the exponent modulo $\phi(125)=100$. Then, you can repeat a similar thing.

Hope this helps. :)

$\endgroup$
2
  • $\begingroup$ I tried it and couldn't reach to a conclusion, if you don't mind can you post the solution? $\endgroup$
    – NOT ACID
    Commented May 16 at 10:52
  • 1
    $\begingroup$ @NOTACID Just repeat the idea: For $2008^{2007^{2006^\cdots}}\bmod{1000}$, the remainder $\bmod 8$ is clear and it suffices to find $2008^{2007^{2006^\cdots}}\bmod{125}$. For the latter, you need $2007^{2006^{2005^\cdots}}\bmod{100}$. i.e., $\bmod 4$ and $\bmod{25}$. For the latter, you need $2006^{2005^{2004^\cdots}}\bmod{20}$, i.e., $\bmod 4$ (easy) and $\bmod 5$. For the latter, sou need $2005^{2004^{2003^\cdots}}\bmod{4}$, which is easy. $\endgroup$
    – Hagen von Eitzen
    Commented May 16 at 11:26
1
$\begingroup$

Let's look at a simpler example: what is the last digit of $8^{7^{6^{\cdots^{2^{1}}}}}$? Well, using the mentioned property:

$$\begin{align}8^{7^{6^{\cdots^{2^{1}}}}}\mod 10 &\equiv 8\hat{}\left({7^{6^{\cdots^{2}}}\mod\varphi(10)}\right)\mod 10 \equiv\tag1\\ &\equiv 8\hat{}\left({7^{6^{\cdots^{2}}}\mod4}\right)\mod 10\equiv\tag2\\ &\equiv8\hat{}\left({7\hat{}\left({6^{5^{\cdots^{2}}}}\mod 2\right)\mod4}\right)\mod 10\equiv\tag3\\ &\equiv 8\hat{}\left({7^0\mod4}\right)\mod 10\equiv\tag4\\ &\equiv8^1\mod 10\equiv8\end{align}$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .