cyberangles blog

Find Last Digit of \(a^b\) for Large Numbers

When dealing with large numbers (a) and (b), calculating (a^b) directly is often impractical due to memory and computational limitations. However, we are often interested only in the last digit of (a^b). This blog post will explore various techniques to efficiently determine the last digit of (a^b) without computing the entire power.

2026-07

Table of Contents#

  1. Pattern Recognition
  2. Modular Arithmetic Approach
  3. Example Usage
  4. Best Practices
  5. Common Pitfalls
  6. References

1. Pattern Recognition#

The last digit of powers of a number (a) often follows a repeating pattern. For example:

  • Consider (a = 2):

    • (2^1=2) (last digit (2))
    • (2^2 = 4) (last digit (4))
    • (2^3=8) (last digit (8))
    • (2^4 = 16) (last digit (6))
    • (2^5=32) (last digit (2))
    • The pattern for the last digit of powers of (2) is (2, 4, 8, 6) and it repeats every (4) exponents.

  • For (a = 3):

    • (3^1 = 3) (last digit (3))
    • (3^2=9) (last digit (9))
    • (3^3 = 27) (last digit (7))
    • (3^4=81) (last digit (1))
    • (3^5 = 243) (last digit (3))
    • The pattern for the last digit of powers of (3) is (3, 9, 7, 1) and it repeats every (4) exponents.

In general, for a single - digit number (a) (where (a\in{0,1,\cdots,9})), we can find the cycle length (l) of the last - digit pattern. Then, we can use the exponent (b) modulo (l) to find the corresponding last digit.

2. Modular Arithmetic Approach#

We know that the last digit of a number (n) is equivalent to (n\bmod{10}). So, to find the last digit of (a^b), we can compute (a^b\bmod{10}).

We can use the property of modular exponentiation: (a^b\bmod{m}=( (a\bmod{m})^b)\bmod{m}). First, reduce (a) modulo (10). Let (a'=a\bmod{10}). Then, we need to compute (a'^b\bmod{10}).

We can further optimize this using the fact that for (a'\in{0,1,\cdots,9}):

  • If (a' = 0), then (a'^b\bmod{10}=0) for (b\geq1)
  • If (a' = 1), then (a'^b\bmod{10}=1) for all (b)
  • For other values of (a'), we can use the cycle detection.

Another way is to use the binary exponentiation (also known as exponentiation by squaring) algorithm to compute (a'^b\bmod{10}) efficiently.

The binary exponentiation algorithm works as follows:

def mod_pow(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent = exponent // 2
        base = (base * base) % mod
    return result

3. Example Usage#

Example 1: Find the last digit of (2^{100})

  • First, (a = 2), (b = 100). Since (a\bmod{10}=2)
  • The cycle length of (2) is (4) (as we saw earlier). (100\bmod{4}=0). When the remainder is (0), we take the last element of the cycle. For the cycle (2,4,8,6), the last element is (6)
  • Using modular exponentiation: (2^{100}\bmod{10}). (2^{100}=(2^4)^{25}). (2^4 = 16), (16\bmod{10}=6). ((6)^{25}\bmod{10}). Since (6^n\bmod{10}=6) for (n\geq1), the last digit is (6)

Example 2: Find the last digit of (12345^{6789})

  • First, (a = 12345), (a\bmod{10}=5)
  • For (a'=5), (5^n\bmod{10}=5) for (n\geq1). So the last digit of (12345^{6789}) is (5)

4. Best Practices#

  • Reduce (a) first: Always start by reducing (a) modulo (10). This simplifies the subsequent calculations.
  • Handle special cases first: Check if (a\bmod{10}) is (0) or (1) immediately, as these cases have straightforward solutions.
  • Use efficient algorithms: When implementing the solution in code, use the binary exponentiation algorithm for modular exponentiation. It has a time complexity of (O(\log b)), which is much more efficient than the naive (O(b)) approach (where we multiply (a) by itself (b) times).

5. Common Pitfalls#

  • Forgetting to reduce (a) modulo (10): If you don't reduce (a) first, you may end up with very large intermediate values (even when using modular arithmetic on the exponentiated result), which can lead to unnecessary computational overhead or even overflow in some programming languages.
  • Incorrect cycle length calculation: Make sure to accurately determine the cycle length for the non - special cases ((a\bmod{10}\notin{0,1})). For example, for (a = 7), the cycle length is (4) ((7,9,3,1)), but if you miscalculate the cycle, you will get the wrong last digit.

References#