How to find the units digit of a certain power in a simplest way

Question

How to find out the units digit of a certain number (e.g. 3 power 2011). What logic should I use to find the answer to this problem?

Answer 1

For base 3:

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...

That is the units digit has only 4 possibilities and then it repeats in ever the same cycle.

With the help of Euler's theorem we can show that this holds for any integer n, meaning their units digit will repeat after at most 4 consecutive exponents. Looking only at the units digit of an arbitrary product is equivalent to taking the remainder of the multiplication modulo 10, for example:

2^7 % 10 = 128 % 10 = 8 

It can also be shown (and is quite intuitive) that for an arbitrary base, the units digit of any power will only depend on the units digit of the base itself - that is 2013^2013 has the same units digit as 3^2013.

We can exploit both facts to come up with an extremely fast algorithm (thanks for the help - with kind permission I may present a much faster version).

The idea is this: As we know that for any number 0-9 there will be at most 4 different outcomes, we can as well store them in a lookup table:

{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4, 
  5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }

That's the possible outcomes for 0-9 in that order, grouped in fours. The idea is now for an exponentiation n^a to

• first take the base mod 10 => := i
• go to index 4*i in our table (it's the starting offset of that particular digit)
• take the exponent mod 4 => := off (as stated by Euler's theorem we only have four possible outcomes!)
• add off to 4*i to get the result

Now to make this as efficient as possible, some tweaks are applied to the basic arithmetic operations:

• Multiplying by 4 is equivalent to shifting two to the left ('<< 2')
• Taking a number a % 4 is equivalent to saying a&3 (masking the 1 and 2 bit, which form the remainder % 4)

---

The algorithm in C:

static int table[] = {
    0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4, 
    5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};

int /* assume n>=0, a>0 */ 
unit_digit(int n, int a)
{
    return table[((n%10)<<2)+(a&3)];
}

---

Proof for the initial claims

From observing we noticed that the units digit for 3^x repeats every fourth power. The claim was that this holds for any integer. But how is this actually proven? As it turns out that it's quite easy using modular arithmetic. If we are only interested in the units digit, we can perform our calculations modulo 10. It's equivalent to say the units digit cycles after 4 exponents or to say

a^4 congruent 1 mod 10

If this holds, then for example

a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10

that is, a^5 yields the same units digit as a^1 and so on.

From Euler's theorem we know that

a^phi(10) mod 10 = 1 mod 10

where phi(10) is the numbers between 1 and 10 that are co-prime to 10 (i.e. their gcd is equal to 1). The numbers < 10 co-prime to 10 are 1,3,7 and 9. So phi(10) = 4 and this proves that really a^4 mod 10 = 1 mod 10.

The last claim to prove is that for exponentiations where the base is >= 10 it suffices to just look at the base's units digit. Lets say our base is x >= 10, so we can say that x = x_0 + 10*x_1 + 100*x_2 + ... (base 10 representation)

Using modular representation it's easy to see that indeed

x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10  

where a_i are coefficients that include powers of x_0 but finally not relevant since the whole product a_i * (10 * x_i)^y-i will be divisible by 10.

Answer 2

You should look at Modular exponentiation. What you want is the same of calculating n^e (mod m) with m = 10. That is the same thing as calculating the remainder of the division by ten of n^e.

You are probably interested in the Right-to-left binary method to calculate it, since it's the most time-efficient one and the easiest not too hard to implement. Here is the pseudocode, from Wikipedia:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result = (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

After that, just call it with modulus = 10 for you desired base and exponent and there's your answer.

EDIT: for an even simpler method, less efficient CPU-wise but more memory-wise, check out the Memory-efficient section of the article on Wikipedia. The logic is straightforward enough:

function modular_pow(base, exponent, modulus)
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c