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.
Continue reading …
How can you tell if a number is a power of two?
That’s easy if it’s in the form 2n, where n is an integer. For example, 212, 20, and 2-37 are powers of two. That is by definition. But what about arbitrary positive numbers like 16,392, 524,288, or 0.00390625? Are they powers of two? Here’s how to tell — if they can be simplified to the form 2n, they are; if they can’t, they’re not.
Continue reading …
Powers of two can be combined, under the laws of exponents, to create other powers of two. Under these rules, you can multiply powers of two, divide powers of two, or raise a power of two to a power and still get another power of two. You can combine these rules to create complicated expressions, expressions that result in a single power of two. For example,
.
The laws of exponents apply generally to any base; two is no different. But since we’re interested in powers of two, we’ll couch them in terms of powers of two. Once we explain the laws in this way, you’ll understand the math behind the example above.
Continue reading …
