Question

Find the last three digits of 9^8^7^6^5^4^9.

Answer 1

So, I need to find mod 125 and 8.
For 8 it's easy - it's 1.
However, what is for 125?
I don't understand how to solve it from: 6^5^4^9 mod 16. (used totient function to climb the tower of exponents)

Answer 2

Is this from textbook or you have cooked it up ?

Answer 3

This one is textbook one. ;)

Answer 4

Hm, perhaps I noticed something?
6 is same as -10 in mod 16, and 5^4^9 is an odd number, so -10^5^4^9 is congruent to -10 or to 6 in mod 16? Is it right?

Answer 5

After following that and doing some ugly things I arrived at an answer of 66, is it right?

Answer 6

And last three digits are 441?

Answer 7

Can you show me how you climbed the tower ? I don't get why you're considering mod 16

Answer 8

Well, we need 9^8^7^6^5^4^9 mod 125. phi(125)= 100, so 8^7^6^5^4^9 mod 100; phi(100)=40, so 7^6^5^4^9 mod 40; phi(40)=16, so 6^5^4^9 mod 16? Or is it wrong?

Answer 9

Ohh I see where I made a mistake.

Answer 10

That's sad, I thought that everything was that easy :(
(8 and 100 aren't coprime)

Answer 11

Very good attempt though
Let's see how else can we work this

Answer 12

But hm, we could divide that mod 100 into mod 25 and mod 4. So, mod 4 of 8^7^6^5^4^9 is 0 and 25 and 8 are coprime.

Answer 13

Definitely, looks lengthy hmm

Answer 14

and 7 and 20 are coprime, so climbing even further.

Answer 15

I'll get back on this after dinner.
1 hour or so

Answer 16

Okay!

Answer 17

Found that the answer is 521, going to solve it once more with more attention to see if it's really 521.

Answer 18

Here's sorta some ideas I cooked up. First this is what we want to compute:

\[9^{8^{7^{6^{5^{4^9}}}}} \mod 1000\]

So I thought, well if there's some value n that isn't too hard to find that this is true:

\[9^n \equiv 9 \mod 1000\]

Then that means we only have to find this value:

\[8^{7^{6^{5^{4^9}}}} \mod n\]

Now it seems we can keep repeating the process as far deep in as we need, since we can correspondingly look at
\[8^k \equiv 8 \mod n\] and \[7^{6^{5^{4^9}}} \mod k\] etc to keep going deeper if we like. I dunno if this is useful or not just an interesting observation.

Answer 19

Well, yes. That's what I have been doing with Euler phi function there. It certainly is one way to solve this, not sure if the most efficient one tho ;) (took me around 15 minutes of constant multiplying and dividing numbers)

Answer 20

Finished checking my work, it's 721, not 521. Ehh. Certainly took a lot of work. :/

Answer 21

Oh beats me, I didn't read anything, I don't even remember how to use the phi function to solve these kinds of things anyways haha.

Answer 22

Hey still here ?

Answer 23

You may use your work from your previous problem here :

7^6^5^4^9 = 1000k+601

Answer 24

Thank you! Already solved it in a long way, and tried to solve it in the last problems way. :)

Answer 25

Good