# computing ${{27^{27}}^{27}}^{27}\pmod {10}$

I'm trying to compute the most right digit of ${{27^{27}}^{27}}^{27}$.

I need to compute ${{27^{27}}^{27}}^{27}(\bmod 10)$.

I now that ${{(27)^{27}}^{27}}^{27}(\bmod 10) \equiv{{(7)^{27}}^{27}}^{27} (\bmod 10)$, so now I need to to compute ${({7^{27})}^{27}}^{27} (\bmod 10)$, since $\gcd(7,10)=1$ and $\phi(10)=4$, $7^{27}=7^{24}\cdot 7^3(\bmod 10)=1 \cdot 7^3 (\bmod 10)=3 (\bmod 10)$ - (Fermat theorem), so I am left with computing ${(3^{27}})^{27} (\bmod 10)$, again $\gcd(3,10)=1$, so $3^{27}= 3^{24}\cdot3^3 \equiv 7(\bmod 10)$, so as I see it the final cut should be again $7^{27}$ which I saw it is already $3 (\bmod 10)$.

Is it correct? what is the correct way to do that?

Thanks

• $(7)^{27^{27^{27}}}$ isn't $(7^{27})^{27^{27}}$ – Cocopuffs Jun 24 '12 at 20:13
• Oh no :( What a fatal mistake. What should I do then? – Jozef Jun 24 '12 at 20:18
• Except that I confused notation, so scratch that. (Thanks Cocopuffs). – MGN Jun 24 '12 at 20:18
• @Jozef Your method still works fine. Just figure out what $27^{27^{27}}$ is mod $4$. – Cocopuffs Jun 24 '12 at 20:19
• The $\TeX$ code {{27^{27}}^{27}}^{27} looks as if it meant $((27^{27})^{27})^{27}$, but it comes out looking like $\displaystyle{{27^{27}}^{27}}^{27}$. If you write it as 27^{27^{27^{27}}}, so that it looks right to the naked eye reading the $\TeX$ code, then it looks like this: $\displaystyle 27^{27^{27^{27}}}$, which for some purposes might be considered inferior under the circumstances. – Michael Hardy Jun 24 '12 at 20:23

On the base level, for all $q$ you get $$\forall \ k: \quad a \equiv a - k \cdot q \mod q.$$ Going one level up, as you may know you're not calculating modulo $q$ anymore, but modulo $\phi(q)$: $$\forall \ k: \quad a^{\displaystyle b} \equiv a^{\displaystyle b - k \cdot \phi(q)} \mod q.$$ You can repeat this, and each time you add a $\phi$: $$\forall \ k: \quad a^{\displaystyle b^{\displaystyle c}} \equiv a^{\displaystyle b^{\displaystyle c - k \cdot \phi(\phi(q))}} \mod q, \\ \forall \ k: \quad a^{\displaystyle b^{\displaystyle c^{\displaystyle d}}} \equiv a^{\displaystyle b^{\displaystyle c^{\displaystyle d - k \cdot \phi(\phi(\phi(q)))}}} \mod q.$$

For $q = 10$ we then have \begin{align} q &= 10, \\ \phi(q) &= 4, \\ \phi(\phi(q)) &= 2, \\\phi(\phi(\phi(q))) &= 1. \end{align} So reducing the numbers on each level separately we get \begin{align} 27^{\displaystyle 27^{\displaystyle 27^{\displaystyle 27}}} &\equiv (27 \bmod 10)^{\displaystyle (27 \bmod 4)^{\displaystyle (27 \bmod 2)^{\displaystyle (27 \bmod 1)}}} \mod 10 \\ &\equiv 7^{\displaystyle 3^{\displaystyle 1^{\displaystyle 0}}} \mod 10 \\ &\equiv 7^{\displaystyle 3^{\displaystyle 1}} \mod 10 \\ &\equiv 7^{\displaystyle 3} \mod 10 \\ &\equiv 3 \mod 10 \end{align}

No such thing as "the" correct way. First we need to know the meaning of the exponential tower, since parentheses have not been inserted. The usual convention is that $a^{b^c}$ means $a^{(b^c)}$. That convention was violated in your argument, so in principle the argument is not correct. A similar error with different numbers can lead to a wrong answer. In this case it didn't. Apart from that, everything was fine.

For $10$, we might as well let our knowledge of the multiplication table guide us. The powers of $7$, starting with $7^1$, end in $7,9,3,1,7,9,\dots$. We are looking at an odd power of $27$, so the answer must be $7$ or $3$.

To decide which, we have to decide whether the exponent $27^{27^{27}}$ is congruent to $1$ or $3$ modulo $4$. Our exponent is $27$ to an odd power, and $27\equiv -1\pmod{4}$. Thus the exponent $27^{27^{27}}$ is also congruent to $-1$ modulo $4$. So the last digit must be $3$.

Remark: One can mention Euler's Theorem. Since $\varphi(10)=4$, the powers of $27$ must, modulo $10$, cycle with period that divides $4$. However, in this case, the cycling is clear.

Note the almost automatic translation of $x\equiv 3\pmod{4}$ to $x\equiv -1\pmod{4}$. This makes computation much more transparent.

Hint $\rm\,\ n\,$ odd $\rm\:\Rightarrow n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}\!\!\!\equiv n^3\!\pmod{10}\$ by $\rm\ \phi(10) = 4,\ \, n^n\equiv n\!\pmod 4\,\$ $[$if tower has $> 1$ term$]$

$\varphi(10)=4$ and $27$ is of the form $(4n+3)\;$. Now ${(4n+3)^{(4n+3)}} \equiv 3(\bmod 4)=4c+3\;$. Clearly, ${(4n+3)}^{(4n+3)^{(4n+3)}}=(4n+3)^{(4c+3)}\equiv 3(\bmod 4)\;$. This will be held true for any length of such powers of the form $4n+3$.

So ${27}^{27^{27^{27}}}\equiv 7^3(\bmod\ 10)\equiv 3(\bmod\ 10)\; \;$ as $7^4\equiv 1(\bmod\ 10)\;$ .