evaluate the last digit of $7^{7^{7^{7^{7}}}}$

I found this puzzle online. Since I'm not good at number theoretic kind of problems I'm going to propose it in this form. If you have a number $x$, in this case $x=7$, how do you evaluate the last digit of $$x^{x^{x^{x^{x}}}}$$ where the number of powers may be $4$ (in this case) or any other, possibly small, number.

-
As a bonus, applying the same reasoning as in the answers, you can show that the last two digits will be 43. –  Raskolnikov Jun 5 '11 at 7:54

Note that the last digit of $7^x$ depends on the remainder $x$ leaves when divided by $4$ i.e. $$7^{4k} \equiv 1 \bmod 10$$ $$7^{4k+1} \equiv 7 \bmod 10$$ $$7^{4k+2} \equiv 9 \bmod 10$$ $$7^{4k+3} \equiv 3 \bmod 10$$

Hence all we are interested is the remainder when $x$ is divided by $4$ i.e in this case the remainder when $7^{7^{7^7}}$ is divided by $4$.

$$7 \equiv -1 \bmod 4$$

Hence $7^{\text{odd number}} \equiv -1 \bmod 4$ and $7^{7^7}$ is odd and hence $7^{7^{7^7}}$ is of the form $4k+3$ and hence $$7^{7^{7^{7^7}}} \text{ has the last digit as }3$$

-

For any $x$ in general (as you asked), the method is similar.

First, let's fix some notation: write $7^{7^{7^{7^7}}}$ as $7 {\uparrow\uparrow} 5$, and similarly a tower of $k$ $x$'s as $x {\uparrow\uparrow} k$. (This operation is called tetration.)

Finding the last digit of $x{\uparrow\uparrow}k$ is the same as finding its value $\bmod 10$. Start looking at the powers of $x$ mod 10: this sequence will always be periodic (with some period at most $4$, it turns out). Say it is periodic with period $m$. In other words, the value of $x^n$ is completely determined by the value of $n \bmod m$.

So now your problem is that of finding the value of $x{\uparrow\uparrow}(k-1) \bmod m$. Again, do the same thing. Look at powers of $x$ mod $m$, they will be periodic with some period, and you want to determine the value of $x{\uparrow\uparrow}(k-2)$ modulo that period. Eventually your problem becomes easy enough, and you can stop.

For your $7 {\uparrow\uparrow} 5$ example, the powers of $7$ are periodic $\bmod 10$ with period $4$. So you want to determine $7 {\uparrow\uparrow} 4 \bmod 4$. The powers of $7$ are periodic $\bmod 4$ with period $2$. So you want to determine $7 {\uparrow\uparrow} 3 \bmod 2$. The powers of $7 \bmod 2$ are periodic with period $1$: a power of $7$ is always $1$. Now you're done: filling in the values backwards, $7 {\uparrow\uparrow} 3 \equiv 1 \mod 2$, so $7 {\uparrow\uparrow} 4 \equiv 3 \mod 4$, so $7 {\uparrow\uparrow} 5 \equiv 3 \mod 10$.

Both the modulus value and the second argument of the tetration decrease at each step, so this method is always guaranteed to terminate soon. The same method works for the last $r$ digits (you want $x{\uparrow\uparrow}k \bmod 10^r$), other bases, etc.

-
Could you please explain filling in the backward part? –  VelvetThunder Apr 11 '12 at 8:51
@Foool:(Step A) As powers of $7$ are always 1 mod 2, $7 {\uparrow\uparrow} 3 \equiv 1 \mod 2$.  (Step B) We want $7 {\uparrow\uparrow} 4 \bmod 4$: Modulo $4$, powers of $7$ are $3, 1, 3, 1$, etc. So 7^(something that is 1 mod 2) is 3, and 7^(something that is 0 mod 2) is 1. Because $7 {\uparrow\uparrow} 4 = 7 ^ {7 {\uparrow\uparrow} 3}$ and the exponent is 1 mod 2, we can conclude that $7 {\uparrow\uparrow} 4 \equiv 3$ (modulo 4).(Step C) We want $7 {\uparrow\uparrow} 5 \bmod 10$: Modulo 10, the powers of 7 are $7, 9, 3, 1, 7, 9, 3, 1$... So 7^(anything that is 3 mod 4) = 3 mod 10. –  ShreevatsaR Apr 11 '12 at 9:46
@Foool: If that's not clear, I can edit the answer to explain in more detail. –  ShreevatsaR Apr 11 '12 at 9:47

A big hint: the powers of $7$, $7^x$, are periodic mod $10$; since $7^4 \equiv 1 \pmod{10}$, every $4$th power of $7$ will end in the same digit; this means that you only need to find out what $7^{7^{7^7}}$ is mod $4$. And since $7^2 \equiv 1 \pmod{4}$, every second power of 7 will be the same mod $4$; so you only need to know what $7^{7^7}$ is mod $2$. And you can probably guess that... :-)

-