What Is the Remainder of a 3000-Layer 7 Power Tower Divided by 11?

[phantasmagoriun]

Crazy Power Tower Problem.

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.
The final answer must be given as a single integer in the range 0-10.


Anyone who can help?

 

[AKG]

Let x = 7 \uparrow \uparrow 2999\ (\mbox{mod }\phi (11)). Prove that 7 \uparrow \uparrow 3000 \equiv 7^x\ (\mbox{mod } 11). This is a starting point, hopefully you can see where to go with this.

 

[phantasmagoriun]

Hey, I'm not really familiar with that notation at all. How would you go about using that and what does the mod 11 mean??

 

[matt grime]

mod 11 means the remainder on division by 11 and presumably the uparrow is hand notaiton for that repeated power you defined.

 

[AKG]

Without knowing what the arrows meant, you could have guessed, couldn't you? Anyways, see here (P.S. I changed the arrows in my post to double arrows in following with Knuth's up-arrow notation - see the link).

 

[StatusX]

To expand a little, say you want to calculate 7^x (mod 11). If you can find some number n₁ with 7^n₁=1 (mod 11), then you only need to look at the exponent mod n₁, because if a=b (mod n₁), it's easy to show that 7^a=7^b (mod 11). As has been pointed out, you can take n₁=\phi(11)=10, where \phi(n) is the Euler totient function.

So now if you want to calculate 7^(7^x) (mod 11), you only need to look at 7^x (mod 10). If you could find an n₂ with 7^n₂=1 (mod 10), you could use the same trick. Continuing this way, you can construct a sequence of positive integers n₁,n₂,n₃,... , and it can be shown that this sequence is decreasing, so it must eventually get down to 1 (you should show this). What can you conclude from this? (note: there would be a problem if one of these n_k were not relatively prime to 7. That won't happen here, but you should understand where the argument breaks down)

 

[phantasmagoriun]

Thanks for the help. I'm going to bring this into my group meeting and see what we can do with it.