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

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.