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?

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

Solution 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

Solution 3

I'm sure there's a proper mathematical way to solve this, but I would suggest that since you only care about the last digit and since in theory every number multiplied by itself repeatedly should generate a repeating pattern eventually (when looking only at the last digit), you could simply perform the multiplications until you detect the first repetition and then map your exponent into the appropriate position in the pattern that you built.

Note that because you only care about the last digit, you can further simplify things by truncating your input number down to its ones-digit before you start building your pattern mapping. This will let you to determine the last digit even for arbitrarily large inputs that would otherwise cause an overflow on the first or second multiplication.

Here's a basic example in JavaScript: http://jsfiddle.net/dtyuA/2/

function lastDigit(base, exponent) {
  if (exponent < 0) {
    alert("stupid user, negative values are not supported");
    return 0;
  }
  if (exponent == 0) {
    return 1;
  }
  var baseString = base + '';
  var lastBaseDigit = baseString.substring(baseString.length - 1);
  var lastDigit = lastBaseDigit;
  var pattern = [];

  do {
    pattern.push(lastDigit);
    var nextProduct = (lastDigit * lastBaseDigit) + '';
    lastDigit = nextProduct.substring(nextProduct.length - 1);
  } while (lastDigit != lastBaseDigit);

  return pattern[(exponent - 1) % pattern.length];
};

function doMath() {
  var base = parseInt(document.getElementById("base").value, 10);
  var exp = parseInt(document.getElementById("exp").value, 10);
  console.log(lastDigit(base, exp));
};

console.log(lastDigit(3003, 5));

Base: <input id="base" type="text" value="3" /> <br> 
Exponent: <input id="exp" type="text" value="2011"><br>
<input type="button" value="Submit" onclick="doMath();" />

And the last digit in 3^2011 is 7, by the way.

Solution 4

The key to solving this type of question lies in Euler's theorem.

This theorem allows us to say that a^phi(m) mod m = 1 mod m, if and only if a and m are coprime. That is, a and m do not divide evenly. If this is the case, (and for your example it is), we can solve the problem on paper, without any programming what so ever.

Let's solve for the unit digit of 3^2011, as in your example. This is equivalent to 3^2011 mod 10.

The first step is to check is 3 and 10 are co-prime. They do not divide evenly, so we can use Euler's theorem.

We also need to compute what the totient, or phi value, is for 10. For 10, it is 4. For 100 phi is 40, 1000 is 4000, etc.

Using Euler's theorem, we can see that 3^4 mod 10 = 1. We can then re-write the original example as:

3^2011 mod 10 = 3^(4*502 + 3) mod 10 = 3^(4*502) mod 10 + 3^3 mod 10 = 1^502 * 3^3 mod 10 = 27 mod 10 = 7

Thus, the last digit of 3^2011 is 7.

As you saw, this required no programming whatsoever and I solved this example on a piece of scratch paper.

Solution 5

We can start by inspecting the last digit of each result obtained by raising the base 10 digits to successive powers:

d      d^2    d^3    d^4    d^5    d^6    d^7    d^8    d^9 (mod 10)
---    ---    ---    ---    ---    ---    ---    ---    ---
0      0      0      0      0      0      0      0      0
1      1      1      1      1      1      1      1      1
2      4      8      6      2      4      8      6      2
3      9      7      1      3      9      7      1      3
4      6      4      6      4      6      4      6      4
5      5      5      5      5      5      5      5      5
6      6      6      6      6      6      6      6      6
7      9      3      1      7      9      3      1      7
8      4      2      6      8      4      2      6      8
9      1      9      1      9      1      9      1      9

We can see that in all cases the last digit cycles through no more than four distinct values. Using this fact, and assuming that n is a non-negative integer and p is a positive integer, we can compute the result fairly directly (e.g. in Javascript):

function lastDigit(n, p) {
    var d = n % 10;
    return [d, (d*d)%10, (d*d*d)%10, (d*d*d*d)%10][(p-1) % 4];
}

... or even more simply:

function lastDigit(n, p) {
    return Math.pow(n % 10, (p-1) % 4 + 1) % 10;
}

lastDigit(3, 2011)
/* 7 */

The second function is equivalent to the first. Note that even though it uses exponentiation, it never works with a number larger than nine to the fourth power (6561).

View more solutions

Comments

[aroth]

It works the same for any arbitrary base. Just truncate it to its last digit and apply the same algorithm.

[Tom Zych]

That pretty much is the proper mathematical way to solve it.

[Tom Zych]

Uh oh. Soon you'll be staying up all hours proving theorems, pondering the Riemann zeta function, and maybe even playing Go. Before long you'll be a gibbering wreck, muttering about Laplace transforms and triple integrals. Run away while you can!

[Rafael Almeida]

@Tom: You can refer to my answer for the "generalized" mathematical solution, which fortunately is already build upon several number theory concepts and thus will hopefully avoid the described chaotic scenario (lol).

[samoz]

In your second function, why are you doing n % 10?

[WReach]

@samoz n % 10 makes the function work for numbers with more than one digit. If the input is restricted to a single digit, then it is not necessary.

[emboss]

+1 for Euler's theorem. If you take advantage of it and precalculate the four possible values for 2, 3 and 7, you can do it even faster than this (see my try at it).

[unkulunkulu]

@Rafael, your answer doesn't touch the beautiful idea of detecting the period and then calculating the answer quicker, instead of log(e) in your case this one gives O(m) actually. At least in the case n and m are coprimes.

[Rafael Almeida]

@unkulunkulu you're right about that. Setting modulus = 10 gives you the chance to apply several optimizations. My answer was basically another way of looking at the problem, which I admit is more interesting in a didactic way than in a pragmatic/efficient one.

[unkulunkulu]

@Rafael, you can detect the period even in the case when modulus is not 10, I was trying to say that. But your method is easy to code and decently fast, of course, I'm just saying :D

[Rafael Almeida]

@unkulunkulu yes you can, but you'd have to do it again by hand for each new module you want to use =D

[unkulunkulu]

@Rafael, nooo!!! You can prove the periodic nature of the sequences with any module, then programmatically find the period in general case, not knowing the module in advance.

[Rafael Almeida]

@unkulunkulu then this matter is above my current knowledge then =). What strikes me as a strange thing is that finding the general pattern of an exponentiation for any given module is in fact doing modular exponentiation, the very topic treated by the wikipedia page I linked. But I guess this comment thread has gone too far away from the OP's question to belong here, and not on Math Exchange lol.

[Rafael Almeida]

@unkulunkulu let us continue this discussion in chat

[David Kelley]

These questions come up on the GRE frequently and this is a better answer than I've seen in any study guide. Thank you SO.