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

Copyright © 2008-2015 Exploring Binary

http://www.exploringbinary.com/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^{2009}, without using a computer. 2^{2009} 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^{n} by the exponent of a known, smaller power of two, 2^{a}, getting a quotient q and a remainder r. You then rewrite 2^{n} 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^{2009}, using 2^{5} (32) to reduce the problem at each step:

So , showing that 2^{2009} ends in 2.

The intermediate results — 2^{405}, 2^{81}, 2^{17}, and 2^{5} — 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^{17} 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^{9} (512):

Using 2^{9}, 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^{4} = 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^{2009}. Consulting a table of positive powers of two, find a power of two that ends in 04; for example, 2^{22} (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^{n} mod 10^{m} specifically:

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

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^{2009}

Let’s use this method to find the last digit of 2^{2009}:

- 2
^{2009}= 2^{1024 + 512 + 256 + 128 + 64 + 16 + 8 + 1} - 2
^{2009}= 2^{1024}· 2^{512}· 2^{256}· 2^{128}· 2^{64}· 2^{16}· 2^{8}· 2^{1} - 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

^{4}. Again, that’s because all powers of six end in 6.) - Combine the required powers:

### Example: Find the Last Two Digits of 2^{2009}

Let’s use this method to find the last *two* digits of 2^{2009}:

- 2
^{2009}= 2^{1024 + 512 + 256 + 128 + 64 + 16 + 8 + 1} - 2
^{2009}= 2^{1024}· 2^{512}· 2^{256}· 2^{128}· 2^{64}· 2^{16}· 2^{8}· 2^{1} - 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.)

- 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^{n} 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^{n} are the digits in the table with the label corresponding to that remainder.

For example, let’s find the last digit of 2^{2009}. 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^{2009}. 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^{n}, 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^{2009}. , so the base power of two is 2^{1+0} = 2^{1} = 2. Trivially, we can see the ending digit is 2.

For the last two digits of 2^{2009}, compute . The base power of two is 2^{2+7} = 2^{9}, 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^{2009}. 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^{n} 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:

- Find the last digit of 2
^{497} - Find the last digit of 2
^{20000} - Find the last two digits of 2
^{613} - Find the last two digits of 2
^{512} - Find the last three digits of 2
^{129} - Find the last three digits of 2
^{2009}

### Answers

- 2
- 6
- 92
- 96
- 912
- 512

June 26th, 2010 at 5:35 am

Do these methods work for floating point powers of two as well?

June 26th, 2010 at 10:56 am

jx,

I’ve written about these techniques from the point of view of a human, not a computer. The powers are written with exponents (example: 2

^{8}), not evaluated as they would be in a native computer representation (example: 256).What did you have in mind?

November 27th, 2010 at 10:11 am

Very interesting and thorough.

I feel a bit envious because I saw this for the first time in my daughter’s reflections on a homework problem when she was 12 years old – in 2003. She did also some other interesting relations. But I have never found time to encourage and help her to publish it…Anyway, I feel proud of her. Now I think it is worth going trough her old notes because she did some other interesting thigs too.

November 27th, 2010 at 10:42 am

Dimitrina,

I hope that her mathematical talents were recognized and nurtured by her teachers, and I hope she is still interested in math (and I hope she is pursuing a math related career!)

Thanks for the feedback.

November 27th, 2010 at 12:55 pm

Hi Rick,

Yes, indeed – now she is istudyng Maths&Philosophy at Oxford,UK

September 12th, 2011 at 11:24 pm

hi this is very good and interesting. it is useful for all mathematics lovers.

September 24th, 2011 at 1:50 am

These are clearly shown for powers of two.Is there any book which has all the workouts of such problems.

September 24th, 2011 at 10:08 am

@Jagan,

Do you mean for other powers? I don’t know of a particular book that covers it (but if one exists, it will be a book about number theory).

September 26th, 2011 at 1:04 am

Thank you sir for the reply.Yes sir they come under Number theory and i have a book by Tom M Apostol but however they mainly discuss about the theory, so i have asked that question.Thank you sir.

September 9th, 2012 at 2:40 pm

how to calculate last 8 digits of 2 raised to power of 1024?? Thanks in advance….

September 9th, 2012 at 11:45 pm

@ajit,

I’m inclined to use the “successive squaring” method. Build a list of powers of two raised to powers of two mod 10^8. Since 1024 is itself a power of two, you will have your answer immediately when you finish the list (no combining required). Give it a try and let me know how it works out.