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

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 22009, without using a computer. 22009 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 10m.

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 10m 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 2n by the exponent of a known, smaller power of two, 2a, getting a quotient q and a remainder r. You then rewrite 2n as (2a)q · 2r.

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 22009, using 25 (32) to reduce the problem at each step:

  • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv {\left(2^{5}\right)}^{401} \cdot2^4 \equiv 2^{401} \cdot2^4 \equiv 2^{405} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^{405} \equiv {\left(2^{5}\right)}^{81} \equiv 2^{81} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^{81} \equiv {\left(2^{5}\right)}^{16} \cdot2^1 \equiv 2^{16} \cdot2^1 \equiv 2^{17} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^{17} \equiv {\left(2^{5}\right)}^{3} \cdot2^2 \equiv 2^{3} \cdot2^2 \equiv 2^{5} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^5 \equiv \textbf{2} \pmod{10}}}}

So \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 2 \pmod{10}}}}, showing that 22009 ends in 2.

The intermediate results — 2405, 281, 217, and 25 — are all congruent, ending in 2. If you recognize this along the way, you can stop. For example, if you happen to know that 217 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 29 (512):

  • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv {\left(2^{9}\right)}^{223} \cdot2^2 \equiv 2^{223} \cdot2^2 \equiv 2^{225} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^{225} \equiv {\left(2^{9}\right)}^{25} \equiv 2^{25} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^{25} \equiv {\left(2^{9}\right)}^{2} \cdot2^7 \equiv 2^{2} \cdot2^7 \equiv 2^{9} \pmod{10}}}}
  • \mbox{\footnotesize{\displaystyle{2^9 \equiv \textbf{2} \pmod{10}}}}

Using 29, 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 24 = 16. The first step would give:

\mbox{\footnotesize{\displaystyle{2^{2009} \equiv {\left(2^{4}\right)}^{502} \cdot2^1 \equiv 6^{502} \cdot2^1 \pmod{10}}}}

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: \mbox{\footnotesize{\displaystyle{6 \cdot 2 \equiv 2 \pmod{10}}}}.

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 2y using the laws of exponents.

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

  • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv {\left(2^{22}\right)}^{91} \cdot 2^7 \equiv 4^{91} \cdot 2^7 \equiv 2^{182} \cdot 2^7 \equiv 2^{189} \pmod{100}}}}
  • \mbox{\footnotesize{\displaystyle{2^{189} \equiv {\left(2^{22}\right)}^{8} \cdot 2^{13} \equiv 4^8 \cdot 2^{13} \equiv 2^{16} \cdot 2^{13} \equiv 2^{29} \pmod{100}}}}
  • \mbox{\footnotesize{\displaystyle{2^{29} \equiv 2^{22} \cdot 2^7 \equiv 4 \cdot 2^7 \equiv 2^2 \cdot 2^7 \equiv 2^9 \pmod{100}}}}
  • \mbox{\footnotesize{\displaystyle{2^9 \equiv \textbf{12} \pmod{100}}}}

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 2m and convert it to 2y 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 2n mod 10m specifically:

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

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 22009

Let’s use this method to find the last digit of 22009:

  1. 22009 = 21024 + 512 + 256 + 128 + 64 + 16 + 8 + 1
  2. 22009 = 21024 · 2512 · 2256 · 2128 · 264 · 216 · 28 · 21
  3. Create a list of powers of two raised to powers of two, mod 10:
    • \mbox{\footnotesize{\displaystyle{2^1 \equiv 2 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^2 \equiv 4 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^4 \equiv 4^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^8 \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{16} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{32} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{64} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{128} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{256} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{512} \equiv 6^2 \equiv 6 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{1024} \equiv 6^2 \equiv 6 \pmod{10}}}}

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

  4. Combine the required powers:
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 2^{1024} \cdot 2^{512} \cdot 2^{256} \cdot 2^{128} \cdot 2^{64} \cdot 2^{16} \cdot 2^8 \cdot 2^1 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 \cdot 2 \pmod{10}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 6^7 \cdot 2  \equiv 6 \cdot 2 \equiv \textbf{2} \pmod{10}}}}

Example: Find the Last Two Digits of 22009

Let’s use this method to find the last two digits of 22009:

  1. 22009 = 21024 + 512 + 256 + 128 + 64 + 16 + 8 + 1
  2. 22009 = 21024 · 2512 · 2256 · 2128 · 264 · 216 · 28 · 21
  3. Create a list of powers of two raised to powers of two, mod 100:
    • \mbox{\footnotesize{\displaystyle{2^1 \equiv 2 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^2 \equiv 4 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^4 \equiv 16 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^8 \equiv 16^2 \equiv 56 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{16} \equiv 56^2 \equiv 36 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{32} \equiv 36^2 \equiv 96 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{64} \equiv 96^2 \equiv 16 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{128} \equiv 16^2 \equiv 56 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{256} \equiv 56^2 \equiv 36 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{512} \equiv 36^2 \equiv 96 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{1024} \equiv 96^2 \equiv 16 \pmod{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:
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 2^{1024} \cdot 2^{512} \cdot 2^{256} \cdot 2^{128} \cdot 2^{64} \cdot 2^{16} \cdot 2^8 \cdot 2^1 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 16 \cdot 96 \cdot 36 \cdot 56 \cdot 16 \cdot 36 \cdot 56 \cdot 2 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv (16 \cdot 96) \cdot (36 \cdot 56) \cdot (16 \cdot 36) \cdot (56 \cdot 2) \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 36 \cdot 16 \cdot 76 \cdot 12 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv (36 \cdot 16) \cdot (76 \cdot 12) \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv 76 \cdot 12 \pmod{100}}}}
    • \mbox{\footnotesize{\displaystyle{2^{2009} \equiv \textbf{12} \pmod{100}}}}

(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·5m-1, starting at 2m. Powers of two that differ in their exponents by 4·5m-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 10m 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 2n falls, compute n mod 4·5m-1, or equivalently, find the remainder of n/(4·5m-1). The last m digits of 2n are the digits in the table with the label corresponding to that remainder.

For example, let’s find the last digit of 22009. The last digit of the positive powers of two cycles with length 4, and \mbox{\footnotesize{\displaystyle{2009 \equiv 1 \pmod{4}}}}. 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 22009. The last two digits of the positive powers of two cycle with length 20, and \mbox{\footnotesize{\displaystyle{2009 \equiv 9 \pmod{20}}}}. 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 2n, mod 10m, is congruent to some power of two in the first instance of the cycle; that is, a power of two between 2m 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 2m + j, where j is an offset given by the expression n-m (mod 4·5m-1).

For example, let’s find the last digit of 22009. \mbox{\footnotesize{\displaystyle{2009 $-$ 1 \equiv 0 \pmod{4}}}}, so the base power of two is 21+0 = 21 = 2. Trivially, we can see the ending digit is 2.

For the last two digits of 22009, compute \mbox{\footnotesize{\displaystyle{2009 $-$ 2 \equiv 7 \pmod{20}}}}. The base power of two is 22+7 = 29, 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·5m-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 22009. 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 2n mod 10m. 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 2497
  2. Find the last digit of 220000
  3. Find the last two digits of 2613
  4. Find the last two digits of 2512
  5. Find the last three digits of 2129
  6. Find the last three digits of 22009

Answers

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

11 Responses to “How to Find the Last Digits of a Positive Power of Two”

  1. jx Says:

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

  2. Rick Regan Says:

    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: 28), not evaluated as they would be in a native computer representation (example: 256).

    What did you have in mind?

  3. Dimitrina Stavrova Says:

    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.

  4. Rick Regan Says:

    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.

  5. Dimitrina Stavrova Says:

    Hi Rick,

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

  6. subbareddy Says:

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

  7. Jagan Mohan Says:

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

  8. Rick Regan Says:

    @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).

  9. Jagan Mohan Says:

    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.

  10. ajit Says:

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

  11. Rick Regan Says:

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

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php