1
$\begingroup$

To find last digit of $a^b$ I just need take the unit digit of $a$ and two last digits of $b$ and then follow patterns for different unit digits $0...9$. What if $b$ has own power that has another power and so on? For example how can I calculate $$123232^{694022^{140249}} \mod 10\:\:? $$

$\endgroup$
  • 1
    $\begingroup$ Do you know Fermat Theorem for congruences? $\endgroup$ – Alessandro Cigna Sep 2 at 7:26
  • $\begingroup$ @Alessandro Cigna not yet $\endgroup$ – Evgeni Nabokov Sep 2 at 8:04
  • $\begingroup$ Several pointers in this mother thread and also those linked to it. $\endgroup$ – Jyrki Lahtonen Sep 2 at 8:16
  • 1
    $\begingroup$ Possible duplicate of How do I compute $a^b\,\bmod c$ by hand? $\endgroup$ – Jyrki Lahtonen Sep 2 at 8:16
  • $\begingroup$ @JyrkiLahtonen It is your duty to give a specific link that you believe answers the question, not a link to motley methods that may or may not apply. Askers deserve much better than "maybe you can compose an answer using some general methods here". One could dismiss almost all ENT questions that way, e.g. "apply the fundamental theorem of arithmetic ...". But that would be a disaster pedagogically. History has shown you have much distaste for these types of questions. Perhaps you should do the honorable thing and abstain from exercising that extreme bias. $\endgroup$ – Bill Dubuque Sep 2 at 17:29
7
$\begingroup$

All that matters is the value of $a_1$ mod $10$, the value of $a_2$ mod $4$, and whether $a_3$ is even or odd, even if the tower goes higher.

Consider $a_1^{a_2^{\vdots^{a_n}}}$. I assume $n\geq3$ and all the $a_i$ are greater than $1$. For ease of notation, let $b=a_2^{a_3^{\vdots^{a_n}}}$.

  • If $a_1\equiv0$ mod $10$, then $a_1^{a_2^{\vdots^{a_n}}}\equiv0$ mod $10$. So for all that follow, assume $10$ does not divide $a_1$.
  • If $a_1\equiv5$ mod $10$, then any power of $a_1$ is also $5$ mod $10$. So for all that follow, assume $5$ does not divide $a_1$.
  • If $a_1\equiv6$ mod $10$, then any power of $a_1$ is also $6$ mod $10$. So for all that follow, assume $a_1\not\equiv6$ mod $10$.
  • If $a_1\equiv4$ or $a_1\equiv8$ mod $10$, then powers of $a_1$ alternate between $a_1$ and $6$ mod $10$. So all that matters is whether $a_2$ is even or odd. If $a_2$ is even, then $a_1^{a_2^{\vdots^{a_n}}}\equiv6$ mod $10$. Otherwise, $a_1^{a_2^{\vdots^{a_n}}}\equiv a_1$ mod $10$.
  • If $a_1\equiv2$ mod $10$, then powers of $a_1$ cycle $(2,4,8,6)$ mod $10$. So you need to know what $b$ is mod $4$.
    • If $a_2\equiv0$ mod $4$, then $b\equiv0$ mod $4$, and $a_1^{a_2^{\vdots^{a_n}}}\equiv 6$ mod $10$.
    • If $a_2\equiv2$ mod $4$, then $a_3>1$ by assumption, and so $b\equiv0$ mod $4$. This means $a_1^{a_2^{\vdots^{a_n}}}\equiv 6$ mod $10$.
    • If $a_2\equiv1$ mod $4$, then any power of $a_2$ is $1$ mod $4$ as well, and $a_1^{a_2^{\vdots^{a_n}}}\equiv 2$ mod $10$.
    • If $a_2\equiv3$ mod $4$, then powers of $a_2$ alternate between $1$ and $3$ mod $4$. So if $a_3$ is even, $b\equiv 1$ mod $4$ and $a_1^{a_2^{\vdots^{a_n}}}\equiv 2$ mod $10$. And if $a_3$ is odd, $b\equiv 3$ mod $4$ and $a_1^{a_2^{\vdots^{a_n}}}\equiv 8$ mod $10$.

Now we may assume $a_1$ is relatively prime to $10$. It is $1$, $3$, $7$, or $9$ mod $10$. Now we have Euler's Theorem saying $$a_1^b\equiv a_1^{b\mod{\varphi(10)=4}}$$

So we care what is $b$ mod $4$. We have already studied that above.

  • If $a_2\equiv0$ mod $4$, then $b\equiv0$ mod $4$, and $a_1^{a_2^{\vdots^{a_n}}}\equiv 1$ mod $10$.
  • If $a_2\equiv2$ mod $4$, then $a_3>1$ by assumption, and so $b\equiv0$ mod $4$. This means $a_1^{a_2^{\vdots^{a_n}}}\equiv 1$ mod $10$.
  • If $a_2\equiv1$ mod $4$, then any power of $a_2$ is $1$ mod $4$ as well, and $a_1^{a_2^{\vdots^{a_n}}}\equiv a_1$ mod $10$.
  • If $a_2\equiv3$ mod $4$, then powers of $a_2$ alternate between $1$ and $3$ mod $4$. So if $a_3$ is even, $b\equiv 1$ mod $4$ and $a_1^{a_2^{\vdots^{a_n}}}\equiv a_1$ mod $10$. And if $a_3$ is odd, $b\equiv 3$ mod $4$ and $a_1^{a_2^{\vdots^{a_n}}}\equiv a_1^3$ mod $10$.

I think that covers all scenarios. For your example, $123232^{694022^{140249}}$ has $a_1\equiv2$ mod $10$. And it has $a_2\equiv2$ mod $4$. So the above outlines how the result is $6$ mod $10$.

Here is a table for the last digit of $a_1^{a_2^{\vdots^{a_n}}}$ based on the above.

$$ \begin{array}{c|c} a_3\text{ even} & a_3\text{ odd}\\ \begin{array}{cc} &a_2\mod 4\\ a_1\mod 10& \begin{array}{c|c} &\begin{array}{cccc} 1&2&3&4 \end{array}\\ \hline 1&\begin{array}{cccc} 1&1&1&1 \end{array}\\ 2&\begin{array}{cccc} 2&6&2&6 \end{array}\\ 3&\begin{array}{cccc} 3&1&3&1 \end{array}\\ 4&\begin{array}{cccc} 4&6&4&6 \end{array}\\ 5&\begin{array}{cccc} 5&5&5&5 \end{array}\\ 6&\begin{array}{cccc} 6&6&6&6 \end{array}\\ 7&\begin{array}{cccc} 7&1&7&1 \end{array}\\ 8&\begin{array}{cccc} 8&6&8&6 \end{array}\\ 9&\begin{array}{cccc} 9&1&9&1 \end{array}\\ 0&\begin{array}{cccc} 0&0&0&0 \end{array}\\ \end{array} \end{array} & \begin{array}{cc} &a_2\mod 4\\ a_1\mod 10& \begin{array}{c|c} &\begin{array}{cccc} 1&2&3&4 \end{array}\\ \hline 1&\begin{array}{cccc} 1&1&1&1 \end{array}\\ 2&\begin{array}{cccc} 2&6&6&6 \end{array}\\ 3&\begin{array}{cccc} 3&1&7&1 \end{array}\\ 4&\begin{array}{cccc} 4&6&4&6 \end{array}\\ 5&\begin{array}{cccc} 5&5&5&5 \end{array}\\ 6&\begin{array}{cccc} 6&6&6&6 \end{array}\\ 7&\begin{array}{cccc} 7&1&3&1 \end{array}\\ 8&\begin{array}{cccc} 8&6&8&6 \end{array}\\ 9&\begin{array}{cccc} 9&1&9&1 \end{array}\\ 0&\begin{array}{cccc} 0&0&0&0 \end{array}\\ \end{array} \end{array} \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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