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

Copyright © 2008-2016 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.

February 23rd, 2015 at 5:15 pm

From a math illiterate … divined by staring into Excel. (If anyone else has posted this please ignore — I did not read through all comments.)

2 ^ 1 = 2

2 ^ 2 = 4

2 ^ 3 = 8

2 ^ 4 = 16

2 ^ 5 = 32

2 ^ 6 = 64

2 ^ 7 = 128

2 ^ 8 = 256

Last Number Pattern: [2,4,8,6],[2,4,8,6],[2,4,….

Every 4th number has its last digit as a 6.

To find 2^2020 last digit, let us divide 2020 by 4, and we see 2020 / 4 evenly divides with no remainder, so must be falling on a number with last digit 6.

2^2019 last digit, 2019/ 4 will leave a fraction of 0.75 (i.e 3/4) which points us to 8, the 3rd number in our set of 4 possible last digits.

A fraction of .50 (i.e. 2/4) indicates 4.

A fraction of .25 (i.e. 1/4) indicates 2.

February 23rd, 2015 at 9:37 pm

@Clifford,

You are using what I call the “table method” in section “3. Cyclic Powers” (using m=1).

January 16th, 2016 at 7:11 am

Wouldn’t it be faster & easier to modulate the exponent first?

Power residues start to repeat as soon as they make one full turn around the modulus, so there’s no point in dealing with bigger exponents anyway. Just calculate the remainder of the exponent in the particular modulus (10, 100 etc.) and this would save you a lot of work to begin with.

For your example:

2^2009 ≡ 2^9 (mod 10)

and you can jump all over your algorithm up to its very end 😉

Just take the last digit of the exponent, which is equivalent of taking 2009 mod 10; in other words: 2009 ≡ 9 (mod 10).

Since

2^2009 ≡ 2^9 (mod 100)

and

2^2009 ≡ 2^9 (mod 1000)

as well, we just need to know that:

2^9 ≡ 12 (mod 100)

and

2^9 ≡ 512 (mod 1000)

to get the last three digits, so let’s use a different example:

2^1234

To get its last digit:

2^1234 ≡ 2^4 ≡ 6 (mod 10)

To get the two last digits of 2^1234 is the same as getting the two last digits of 2^34, because:

2^1234 ≡ 2^34 (mod 100)

It’s easier to begin with that, than doing all the steps of your algorithm.

Of course there’s still a problem of finding the last two digits of 2^34, because we cannot reduce the exponent any further (it’s already a least residue in the modulus 100). So you can

nowproceed with your algorithms, or simply use the well-knownfastalgorithm formodular exponentiation. It works pretty much the same way thefastalgorithm for theusualexponentiation. It uses the observation that, if you have, for example, something like this:2^17 = 2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2×2

then you can group the numbers this way:

2^17 = (2×2×2×2×2×2×2×2)×(2×2×2×2×2×2×2×2)×2

and then the result of the first parenthesis is exactly the same as of the second parenthesis, so there is no point in calculating it twice. Just calculate it once and square the result (that is, multiply the current result by itself):

2^17 = (2×2×2×2×2×2×2×2)^2 × 2

and of course you can do the same with the content of this parenthesis as well:

2^17 = ((2×2×2×2)×(2×2×2×2))^2 × 2

2^17 = ((2×2×2×2)^2)^2 × 2

and again:

2^17 = (((2×2)×(2×2))^2)^2 × 2

2^17 = (((2×2)^2)^2)^2 × 2

and again:

2^17 = ((((2)×(2))^2)^2)^2 × 2

2^17 = ((((2)^2)^2)^2)^2 × 2

so we end up with 4 squarings (multiplications with itself), and one multiplication by the base (2), which gives 5 multiplications instead of 16.

Now, just replace normal multiplications with multiplication in the modulus 10, or 100, or whatever, to get the fast modular exponentiation 🙂 (or simply reduce the result of each squaring/multiplication by the modulus).

This is pretty similar to what you do already in your algorithm, just faster & more organized, because you don’t need to guess the powers of 2 which end with a particular digit to make it going – you just square your working register in each step, and if there’s a bit set in your exponent, you additionally multiply the working register by your base. This algorithm is logarithmic in the size of the exponent, so it scales very well 🙂

In our example with 2^34 (mod 100), we could proceed further as follows:

2^34 = (2^17)^2 = ((2^16)×2)^2 = (((2^8)^2)×2)^2 =

= ((((2^4)^2)^2)×2)^2 = (((((2^2)^2)^2)^2)×2)^2

Now unroll it step by step, reducing by the modulus after each step:

2^34 (mod 100)

(((((2^2)^2)^2)^2)×2)^2 (mod 100)

((((4^2)^2)^2)×2)^2 (mod 100)

(((16^2)^2)×2)^2 (mod 100)

((32^2)×2)^2 (mod 100)

(64×2)^2 (mod 100)

28^2 (mod 100)

84 (mod 100)

and indeed

2^1234 ≡ 2^34 ≡ 84 (mod 100)

so the last two digits of 2^1234 are 84.

January 18th, 2016 at 10:33 am

Awesome article and i am impressed !

Your article really helped me to go through the school assignments and its quite logical ! Can you please publish another article on other no.s (like 3,5,7) ?

Thanx and Appreciate it bro !

February 11th, 2016 at 10:33 am

@SasQ

while e. g.

2^2009 ≡ 2^9 (mod 1000) holds true,

2^2002 ≡ 2^2 (mod 1000) doesn’t