Modular Arithmetic and Exponential Towers: Solving the Power Tower Puzzle

[phantasmagoriun]

Consider an exponential tower of three thousand 7's.
What is the remainder when you divide the tower by 11?
Note that this notation means 7^(7^7) not (7^7)^7. So it's kinda like the Ackermann Function maybe?
The final answer must be given as a single integer in the range 0-10.


Anyone got any ideas?

 

[0rthodontist]

You can just do a (sort of) brute force method:
Find 7 mod 11 = a1
Find 7 ^ a₁ mod 11 = a₂
Find 7 ^ a₂ mod 11 = a₃
...
Find 7 ^ a_(n-1) mod 11 = a_n where a_n = a₁
Then the top of the exponent tower will cycle through the sequence a₁...a_n-1 as you evaluate it and all you have to do is count correctly so you land on the right element of the sequence.

This method is easy by calculator but harder by hand. There is probably a better way to do this.

 

[gnomedt]

Similar to the last post, but try using Euler's theorem perhaps?

There is also an efficient method of doing large modular exponentiation.

 

[NateTG]

\phi(11)=10
So, from Fermat's Little Theorem, we could reduce the last exponent modulo 10 without altering the result.

So, if we knew the remainder of a tower of 2999 7's when divided by 10 then we'd only have one exponentiation left, right?

 

[phantasmagoriun]

Thanks for the help. I'm going to bring this stuff into my group meeting and see what we can do with it. (None of us have seen this type of problem before, nor worked with mod, so hopefully we can figure it out)