8
$\begingroup$

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

  • 0
    @Jozef Right, $a$ should be a unit2012-06-25

4 Answers 4

8

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}

5

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.

5

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

4

$\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)\; $ .