last digit of a^b^c

Question

I've got stuck on this problem :

Given a, b and c three natural numbers (such that 1<= a, b, c <= 10^9), you are supposed to find the last digit of the number a^b^c."

What I've firstly thought was the O(log n) algorithm for raising a at power n.

   int acc=1; //accumulator
   while(n>0) {
        if(n%2==1)
            acc*=a;
        a=a*a;
        n/=2;
    }

Obviously, some basic math might help, like the "last digit" stuff :

Last_digit(2^n) = Last_digit(2^(n%4))

Where n%4 is the remainder of the division n/4

In a nutshell, I've tried to combine these, but I couldn't get on the good way.

Some help would really be apreciated.

Answer 1

Like I mentioned in my comments, this really doesn't have much to do with smart algorithms. The problem can be reduced completely using some elementary number theory. This will yield an O(1) algorithm.

The Chinese remainder theorem says that if we know some number x modulo 2 and modulo 5, we know it modulo 10. So finding a^b^c modulo 10 can be reduced to finding a^b^c modulo 2 and a^b^c modulo 5. Fermat's little theorem says that for any prime p, if p does not divide a, then a^(p-1) = 1 (mod p), so a^n = a^(n mod (p-1)) (mod p). If p does divide a, then obviously a^n = 0 (mod p) for any n > 0. Note that x^n = x (mod 2) for any n>0, so a^b^c = a (mod 2).

What remains is to find a^b^c mod 5, which reduces to finding b^c mod 4. Unfortunately, we can use neither the Chinese remainder theorem, nor Fermat's little theorem here. However, mod 4 there are only 4 possibilities for b, so we can check them separately. If we start with b = 0 (mod 4) or b = 1 (mod 4), then of course b^c = b (mod 4). If we have b = 2 (mod 4) then it is easily seen that b^c = 2 (mod 4) if c = 1, and b^c = 0 (mod 4) if c > 1. If b = 3 (mod 4) then b^c = 3 if c is even, and b^c = 1 if c is odd. This gives us b^c (mod 4) for any b and c, which then gives us a^b^c (mod 5), all in constant time.

Finally with a^b^c = a (mod 2) we can use the Chinese remainder theorem to find a^b^c (mod 10). This requires a mapping between (x (mod 2), y (mod 5)) and z (mod 10). The Chinese remainder theorem only tells us that this mapping is bijective, it doesn't tell us how to find it. However, there are only 10 options, so this is easily done on a piece of paper or using a little program. Once we find this mapping we simply store it in an array, and we can do the entire calculation in O(1).

By the way, this would be the implementation of my algorithm in python:

# this table only  needs to be calculated once
# can also be hard-coded
mod2mod5_to_mod10 = [[0 for i in range(5)] for j in range(2)]
for i in range(10):
    mod2mod5_to_mod10[i % 2][i % 5] = i

[a,b,c] = [int(input()) for i in range(3)]

if a % 5 == 0:
    abcmod5 = 0
else:
    bmod4 = b % 4
    if bmod4  == 0 or bmod4 == 1:
        bcmod4 = bmod4 
    elif bmod4 == 2:
        if c == 1:
            bcmod4 = 2
        else:
            bcmod4 = 0
    else:
        if c % 2 == 0:
            bcmod4 = 1
        else:
            bcmod4 = 3

    abcmod5 = ((a % 5)**bcmod4) % 5

abcmod2 = a % 2

abcmod10 = mod2mod5_to_mod10[abcmod2][abcmod5]

print(abcmod10)

Answer 2

The problem is that b^c may be very large. So you want to reduce it before using the standard modular exponentiation.

You can remark that a^(b^c) MOD 10 can have a maximum of 10 different values.

Because of the pigeonhole principle, there will be a number p such that for some r:

a^r MOD 10 = a^(p+r) MOD 10
p <= 10
r <= 10

This implies that for any q:

a^r MOD 10 = a^r*a^p MOD 10
           = (a^r*a^p)*a^p MOD 10
           = ...
           = a^(r+q*p) MOD 10

For any n = s+r+q*p, with s < p you have:

a^n MOD 10 = a^s*a^(r+q*p) MOD 10
           = a^s*a^r MOD 10 
           = a^((n-r) MOD p)*a^r MOD 10

You can just replace n= (b^c) in the previous equation.

You will only compute (b^c-r) MOD p where p <= 10 which is easily done and then compute a^((b^c-r) MOD p)*a^r MOD 10.