# Power Tower problem HELP!

1. Sep 7, 2006

### 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???

Last edited: Sep 7, 2006
2. Sep 7, 2006

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

Last edited: Sep 8, 2006
3. Sep 8, 2006

### 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??

4. Sep 8, 2006

### matt grime

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

5. Sep 8, 2006

### 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).

6. Sep 8, 2006

### StatusX

To expand a little, say you want to calculate 7^x (mod 11). If you can find some number n1 with 7^n1=1 (mod 11), then you only need to look at the exponent mod n1, because if a=b (mod n1), it's easy to show that 7^a=7^b (mod 11). As has been pointed out, you can take n1=$\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 n2 with 7^n2=1 (mod 10), you could use the same trick. Continuing this way, you can construct a sequence of positive integers n1,n2,n3,... , 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 nk were not relatively prime to 7. That won't happen here, but you should understand where the argument breaks down)

Last edited: Sep 8, 2006
7. Sep 8, 2006

### phantasmagoriun

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