How to Find the Last Digits of a Positive Power of Two

A common exercise in number theory is to find the last digits of a large power, like 2²⁰⁰⁹, without using a computer. 2²⁰⁰⁹ is a 605-digit number, so evaluating it by hand is out of the question. So how do you find its last digits — efficiently?

Modular arithmetic, and in particular, modular exponentiation, comes to the rescue. It provides an efficient way to find the last m digits of a power, by hand, with perhaps only a little help from a pocket calculator. All you need to do is compute the power incrementally, modulo 10^m.

In this article, I will discuss three methods — all based on modular exponentiation and the laws of exponents — for finding the ending digits of a positive power of two. The techniques I use are easily adapted to powers of any number.

1. Ad Hoc Exponentiation

In this method, you reduce a power of two modulo 10^m repeatedly until you get a congruent power, or product of powers, for which the end digits are known — or easily computed. You use your knowledge of smaller powers of two, in conjunction with the power of a power and product of powers rules, to set up easier sub problems to solve.

You start by dividing the exponent of 2ⁿ by the exponent of a known, smaller power of two, 2^a, getting a quotient q and a remainder r. You then rewrite 2ⁿ as (2^a)^q · 2^r.

Finding the Last Digit

I’ve categorized two sub methods of the ad hoc method that make it more systematic when dealing specifically with powers of two. I call them the powers of two method and the powers of six method.

Powers of Two Method

In the powers of two method, you reduce a power of two by using a power of two ending in 2. This reduces the problem at each stage to a smaller power of two, giving the method a recursive feel. The intermediate powers of two are in effect nested.

For example, let’s find the last digit of 2²⁰⁰⁹, using 2⁵ (32) to reduce the problem at each step:

• 
• 
• 
• 
• 

So , showing that 2²⁰⁰⁹ ends in 2.

The intermediate results — 2⁴⁰⁵, 2⁸¹, 2¹⁷, and 2⁵ — are all congruent, ending in 2. If you recognize this along the way, you can stop. For example, if you happen to know that 2¹⁷ is 131,072, you can stop after the third step.

Any power of two ending in 2 works. Here’s how the process goes when using 2⁹ (512):

• 
• 
• 
• 

Using 2⁹, there is one less step, but the arithmetic is slightly harder (division by 9 instead of division by 5).

Powers of Six Method

In the powers of six method, you reduce a power of two using a power of two that ends in 6. This introduces powers of six, which have to be handled separately and combined with the “remainder” powers of two. For example, let’s do our example with 2⁴ = 16. The first step would give:

But wait! All powers of six end in 6 (6 times 6 mod 10 is 6, and around it goes…), so we just turned this into a very simple problem: .

So, while it doesn’t have the elegance of the powers of two method, the powers of six method is simpler.

Finding the Last Two Digits

The powers of six method does not apply to mod 100, but the powers of two method does — indirectly. Although there is no power of two that ends in 02, we can use any two-digit ending that is a power of two; we just convert it to 2^y using the laws of exponents.

Let’s go back to our example, 2²⁰⁰⁹. Consulting a table of positive powers of two, find a power of two that ends in 04; for example, 2²² (4,194,304). Let’s use this to reduce our problem at each step:

• 
• 
• 
• 

Finding the Last m Digits

For the last m digits, find an m-digit power of two (m digits including leading zeros) greater than or equal to 2^m and convert it to 2^y as above. Of course, the remainders will become larger and larger as the modulus increases.

2. Successive Squaring

The method of successive squaring, also called repeated squaring or binary exponentiation, is a very systematic way to do modular exponentiation. It’s a generic four step process applicable to any base and modulus, but here’s how to use it to compute 2ⁿ mod 10^m specifically:

1. Rewrite 2ⁿ so that n is a sum of powers of two (essentially, convert n to binary).
2. Rewrite 2ⁿ using the product of powers rule.
3. Create a list of powers 2²ⁱ mod 10^m, by repeatedly squaring the prior result.
4. Combine, with multiplication mod 10^m, the powers in the list that make up 2ⁿ.

This process is independent of the number of ending digits m, although you have to deal with bigger and bigger numbers as m increases.

Example: Find the Last Digit of 2²⁰⁰⁹

Let’s use this method to find the last digit of 2²⁰⁰⁹:

1. 2²⁰⁰⁹ = 2^{1024 + 512 + 256 + 128 + 64 + 16 + 8 + 1}
2. 2²⁰⁰⁹ = 2¹⁰²⁴ · 2⁵¹² · 2²⁵⁶ · 2¹²⁸ · 2⁶⁴ · 2¹⁶ · 2⁸ · 2¹
3. Create a list of powers of two raised to powers of two, mod 10:
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 

   (I wrote out the whole list for completeness, but it was unnecessary to go beyond 2⁴. Again, that’s because all powers of six end in 6.)

4. Combine the required powers:
   • 
   • 
   • 

Example: Find the Last Two Digits of 2²⁰⁰⁹

Let’s use this method to find the last two digits of 2²⁰⁰⁹:

1. 2²⁰⁰⁹ = 2^{1024 + 512 + 256 + 128 + 64 + 16 + 8 + 1}
2. 2²⁰⁰⁹ = 2¹⁰²⁴ · 2⁵¹² · 2²⁵⁶ · 2¹²⁸ · 2⁶⁴ · 2¹⁶ · 2⁸ · 2¹
3. Create a list of powers of two raised to powers of two, mod 100:
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 
   • 

   (Notice that the powers in this list cycle after a point, so it is not necessary to compute them all.)

4. Combine the required powers:
   • 
   • 
   • 
   • 
   • 
   • 
   • 

(I could have used negative numbers in the intermediate steps to make the math easier; for example, -4 instead of 96. Both are congruent mod 100.)

3. Cyclic Powers

In this method, you exploit the fact that the ending m digits of the positive powers of two repeat in cycles; specifically, cycles of length 4·5^m-1, starting at 2^m. Powers of two that differ in their exponents by 4·5^m-1 have the same ending m digits.

There are two ways to use the cycle information, in techniques I call the table method and the base power method.

Table Method

In the table method, you compute the powers of two mod 10^m in sequence, until the ending digits cycle. You label entries sequentially starting at m, wrapping around 0 to end at m – 1. I’ve created tables for the last one, two, and three ending digits; in other words, tables for powers of two mod 10, mod 100, and mod 1000.

To find where in the cycle your power 2ⁿ falls, compute n mod 4·5^m-1, or equivalently, find the remainder of n/(4·5^m-1). The last m digits of 2ⁿ are the digits in the table with the label corresponding to that remainder.

For example, let’s find the last digit of 2²⁰⁰⁹. The last digit of the positive powers of two cycles with length 4, and . According to the table, a remainder of 1 corresponds to a last digit of 2.

Almost as simply, we can find the last two digits of 2²⁰⁰⁹. The last two digits of the positive powers of two cycle with length 20, and . According to the table, a remainder of 9 corresponds to the ending digits 12.

Finding the Last m Digits

The table method works for any number of ending digits, but beyond two or three, is impractical. The tables grow large, by a factor of five for each additional ending digit.

Base Power Method

Every power of two 2ⁿ, mod 10^m, is congruent to some power of two in the first instance of the cycle; that is, a power of two between 2^m and 2^{(m + 4·5m – 1 – 1)}. You need to determine which power of two in this range it is — what I call the base power of two — and then use another method to find its ending digits.

You can find the base power of two directly: it is 2^{m + j}, where j is an offset given by the expression n-m (mod 4·5^m-1).

For example, let’s find the last digit of 2²⁰⁰⁹. , so the base power of two is 2¹⁺⁰ = 2¹ = 2. Trivially, we can see the ending digit is 2.

For the last two digits of 2²⁰⁰⁹, compute . The base power of two is 2²⁺⁷ = 2⁹, which is small enough to compute directly: 512. The last two digits are 12.

Finding the Last m Digits

The base power method works well for any number of ending digits, assuming n is greater than 4·5^m-1.

Cheating

I said find the last digits without using a computer, right? I wanted to verify my work, so I used PARI/GP to compute 2²⁰⁰⁹. It took an instant — here it is:

58,784,291,598,041,831,640,721,059,900,297,317,581,942,666,346,941,194,264,455,308,125,479,232,583,289,360,069,460,965,699,405,121,019,824,433,389,516,158,094,000,492,490,796,188,432,969,007,685,435,732,643,092,034,554,442,399,887,360,352,654,923,898,902,974,171,610,618,912,504,957,328,187,117,386,950,842,341,026,317,332,718,773,233,103,358,237,779,148,190,179,650,358,079,135,564,562,516,081,648,810,332,848,214,481,400,042,754,868,418,296,221,651,998,157,278,605,568,219,649,390,953,792,425,227,268,163,704,976,021,381,769,156,258,409,778,685,642,966,081,035,151,287,502,869,585,844,829,824,788,935,390,157,871,063,324,138,385,197,912,084,049,961,962,094,914,858,370,754,777,898,867,719,950,514,578,646,749,211,908,564,621,201,347,904,089,822,990,746,021,295,498,658,798,312,326,238,643,788,303,040,512

Summary

The three methods I’ve shown are efficient ways to do modular exponentiation, unlike the straightforward method, which requires n-1 multiplications to compute 2ⁿ mod 10^m. The three methods provide shortcuts to the answer, exploiting knowledge of the laws of exponents and the cycling of ending digits.

Which method should you use? The ad hoc method is the least systematic but allows for case-by-case optimization. The method of successive squaring is the most systematic but may be overkill for certain problems. Learn all three methods to get a deeper understanding, then decide which one you like.

For finding the last digit, I like the ad hoc powers of six method. It is the quickest.

Exercises

For these exercises, use any method you like — or all three if you’re feeling ambitious:

1. Find the last digit of 2⁴⁹⁷
2. Find the last digit of 2²⁰⁰⁰⁰
3. Find the last two digits of 2⁶¹³
4. Find the last two digits of 2⁵¹²
5. Find the last three digits of 2¹²⁹
6. Find the last three digits of 2²⁰⁰⁹

Answers

1. 2
2. 6
3. 92
4. 96
5. 912
6. 512