Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 20 down vote accepted

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$$

share|improve this answer

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.

share|improve this answer
    
Could you please explain filling in the backward part? –  Quixotic 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... :-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.