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$ ?
Best Answer
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.