What is the best algorithm for finding the last digit of an enormous exponent?

Question

I found most answers here not clear enough for my case such as

$$ 123155131514315^{4515131323164343214547} $$

I wrote the $n\bmod10$ in Python and execution time ran out. So I need a faster algorithm or method. Sometimes, the result is incorrect as it failed the test case.

Answer 1

If $a=10q+b$, then $a^n \equiv b^n \bmod 10$, and so it suffices to consider $b^n$, for $b = 0, 1, \dots, 9$.

These powers repeat as follows:

$0^n = 0, 0, \dots $

$1^n = 1, 1, \dots $

$2^n = 2, 4, 8, 6, 2, 4, 8, 6, \dots $

$3^n = 3, 9, 7, 1, 3, 9, 7, 1, \dots $

$4^n = 4, 6, 4, 6, \dots $

$5^n = 5, 5, \dots $

$6^n = 6, 6, \dots $

$7^n = 7, 9, 3, 1, 7, 9, 3, 1,\dots $

$8^n = 8, 4, 2, 6, 8, 4, 2, 6, \dots $

$9^n = 9, 1, 9, 1, \dots $

So, you only have to compute $n \bmod m$, where $m$ is the period corresponding to $b$, and look up the answer in the list above.

Answer 2

First of all, you can replace the base with its $\pmod{10}$ residue. Then you can use the Euler-Fermat theorem: $a^{\varphi(n)}\equiv 1 \pmod{n}$ iff $\gcd(a,n)=1$.

In particular, to determine $a^k \pmod{10}$, you have to first take $a \pmod{10}$. If it is $0$ or $5$, then you are very lucky. If it is $2,4,6,8$, then you are still lucky: the powers of these are also periodic with period $4$, so this case can be treated similarly as the next one (the reason is $\varphi(5)=4$, think about it).

If the residue is reduced, then apply the Euler-Fermat theorem. Then you just need to calculate the exponent mod $\varphi(10)=4$, and replace the exponent by that number.

In fact, there is a typical problem when you need to compute the residue of a tower like $a^{b^{c^\ldots}}$ $\pmod n$. Then you can use the Euler-Fermat theorem iteratively.

Answer 3

The other answers are good for specifically the problem of finding the last digit; and more generally, for modular exponentiation where the divisor is not too large.

But if you want more generally to calculate powers with large exponents, you need to be familiar with Exponentiation by squaring. It works whenever you have a power with an integer exponent, assuming you can do a multiplication relatively fast. The multiplication can be on any group, it needn't be integers or modular numbers. It can handle exponents like 4515131323164343214547 with ease.

Specifically, the complexity is logarithmic in the exponent, rather than linear as in naive exponentiation.

As an added bonus, if multiplication is relatively expensive and the exponent is not too large, you may want to consider optimal Addition-Chain Exponentiation.

Answer 4

The trick is to realize that there is a lot of extraneous information.

We only need the last digit of $123155131514315\equiv 5$ and the remainder when divided by $4$ of $4515131323164343214547\equiv 3$ to know the last digit of $123155131514315^{4515131323164343214547}$ is the same as the last digit of $5^3$. Namely $5$.

....

Only the last digit of $a$ will affect the last digit of $a^b$ so $123155131514315^{4515131323164343214547}$'s last digit is the same as $5^{4515131323164343214547}$s last digit.[1]

Also the last digit repeats every $4$ terms. So the last digit of $a^k$ will be the same as the last digit of $a^{k + 4m}$. Example the last digit of $2^5 = 32$ is the same as the last digit of $2^1 = 2$ and the last digit of $7^{4} =2401 $ is $1$ so the last digit of $7^{10} = 7^6*7^4*7^2*7^4*7^4$ must be the same as the last digit of $7^2$. Namely $9$ and indeed $7^10 = 49*2401*2401 = 282475249$[2]

Now, why we can assume [1] and [2] can be explained in as much or as little detail as you need.

[1]. Using the notation $a \equiv b \mod n$ to mean $a$ and $b$ have the same remainder when divided by $n$ it is a very basic proposition that if $a \equiv b \mod n$ then $a^k\equiv b^k \mod n$ for every positive integer $n$. This is clear as $a = m*n + b$ for some integer $m$ and $a^k = (m*n + b)^k = (mn)^k + k*(mn)^{k-1}b + .... + k(mn)*b^{k-1} + b^{k}$ and $(mn)^k + k*(mn)^{k-1}b + .... + k(mn)*b^{k-1}$ is a multiple of $n$.

[2]. Requires we know a bit more sophisticated number theory namely Eulers's Theorem and the chinese remainder theorem. There are $4$ numbers less than or equal to $10$ that are relatively prime to $10$ ($1$,$3$,$7$,$9$) as so $\phi(10) = 4$ and so Euler's theorem states. That if $n$ and $a$ are relatively prim $a^{\phi(n)} \equiv 1 \mod n$ so $a^{\phi(10) = 4} \equiv 1 \mod 10$ if $a = 1,3,7,9$ and so $a^{4m+k} \equiv (a^4)^m*4^k \equiv 1^m*4^k\equiv 4^k \mod 10$.

On the other hand, if $a$ is not relatively prime to $10$ then ....

Let $a = a'*\gcd(10,a)$ so $a'$ is relatively prime to $10$. And $a^{k + 4m} \equiv a'^{k+4m} * \gcd(10,a)^{k + 4m} \equiv a^k*\gcd(10,a)^{k+4m}\mod 10$. So we just need to show that $\gcd(10,a)^{k+4m}\equiv \gcd(10,a)^k\mod 10$.

Let $\gcd(a,10) = d$ and let $b = \frac {10}d$. So... $b$ and $d$ are relatively prime so $d^{\phi b} \equiv 1 \mod b$. And $b|10$ so $\phi(b)|\phi(10) = 4$. So $d^4 \equiv 1\mod b$ and $d^{k+4m}\equiv d^k \mod b$.

And $d^{k+4m}\equiv d^k \equiv 0 \mod d$.

By the chinese remainder theorem there is unique $x \mod 10$ so that $x\equiv d^k\mod b$ and $x \equiv d^k \mod d$. And both $d^{k+4m}$ and $d^k$ satisfy that. So $d^{k+4m}\equiv d^k \mod 10$.