Calculate the last digit of $a^{b^c}$

Question

I'm doing some programming challenges, and I have to find the last digit of the result from evaluating the expression $a^{b^c}$. The unit tests of this challenge feature very big integers, so calculating the result of this is out of question, the program will crash without a doubt.

So my question is, is there a way to simplify such an expression so I can solve it with the integers given as test inputs, or is there an obvious way to calculate the last digit of the result based on the values of $a$, $b$ and $c$ ?

Answer 1

Let $k$ be the last digit of $a$.

As you know, the last digit of $k^n$ is periodic in $n$ for every $k$. Let $T(k)$ be the period length

Typically, the last digit of $k^n$ has a period like $$[a_1,a_2,\cdots,a_i]$$.

For example, $4^n$ has a period $$[4,6]$$ and $T(4)=2$.

$7^n$ has a period $$[7,9,3,1]$$ and $T(7)=4$.

So, just find the remainder of $b^c$ divided by $T(k)$. Let the remainder be $r$. Then the $r$th term in the period is the last digit of $a^{b^c}$. $r=0$ implies the last term.

---

Finding $r$ is not easy if $b,c$ are large.

Let $r’$ be the remainder of $b$ divided by $T(k)$.

Let $R$ be the remainder of $r’^c$ divided by $T(k)$.

It can be shown that $R=r$.

Since $r’$ is small, computing $R$ is more manageable and doable by hand.

Answer 2

You have to find what $a^{b^c}$ is modulo $10$. To do this, it's enough to find what it is modulo $2$ and then modulo $5$: by the Chinese Remainder Theorem (CRT), $(n\bmod 2, n\bmod 5)$ contains exactly as much information as $n\bmod 10$: $$\matrix{n\bmod 2&n\bmod 5&n\bmod 10\\0&0&0\\1&1&1\\0&2&2\\1&3&3\\0&4&4\\1&0&5\\0&1&6\\1&2&7\\0&3&8\\1&4&9}$$

• $a^{b^c}\bmod 2$ is the parity of the last digit of $a$ (since $0$ to any power stays $0$ and the same for $1$).

• $a^{b^c}\bmod 5$ is $0$ if $a\equiv 0\bmod 5$

• if $a\not \equiv 0\bmod 5$ to compute $a^{b^c}\bmod 5$ you can apply Fermat's Little Theorem: $$a^4\equiv 1\bmod 5$$ and the problem reduces to find $b^c\bmod 4$. This depends only on what $b$ is modulo $4$, and what $c$ is modulo $2$ since all geometric sequences modulo $4$ have period $1$ or $2$. Therefore, you can replace $b$ by its remainder $b'$ in the division by $4$, and $c$ by its parity $c'$ ($0$ if $c$ is even, $1$ otherwise)

  Finally, $a^{b^c}\bmod 5$ is equal to $(a')^{(b')^{c'}}$ where $a'$ is the remainder in the division of $a$ by $5$.