# What is the best algorithm for finding the last digit of an enormous exponent? [duplicate]

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.

## marked as duplicate by Servaes, Daniel Fischer♦Aug 16 at 20:21

• All powers of a number ending in $5$ end in $5$. – lulu Aug 16 at 12:49
• I knew that but this is example. It can be any number. – Masked Man Aug 16 at 12:51
• To calculate $a^b$ modulo $10$ in general, reduce $a$ modulo $10$ and $b$ modulo $4$. If the exponent is now zero, replace it by $4$. This power has the same residue modulo $10$ than the given one. – Peter Aug 16 at 12:55
• If you take any digit then its powers are periodic $\pmod {10}$. If your digit is $3$, say, the last digits go as $\{3,9,7,1,3,9,7,1,\cdots\}$. Thus it really isn't much harder if the last digit is something other than $5$. – lulu Aug 16 at 12:56
• Python's pow function can do modular exponentiation: pow(123155131514315, 4515131323164343214547, 10) – Justin Aug 16 at 16:48

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.

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.

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.

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