Yesterday we saw that must be composite, since

.

Today I’ll talk about a somewhat more intuitive way to see this.

Recall that we can write numbers in base 2, or “binary”, using the digits 0 and 1 (called “bits”, short for *binary digits*) with place values that are powers of two. To avoid confusion, we use a subscript to denote a number written in base 2. For example,

How are Mersenne numbers written in binary? In fact, they are written , with 1 bits. For example, is written in base 2 as . There are a couple ways to see this. First, if you know something about how base-2 arithmetic works, note that adding to a binary number consisting of all ’s will cause a cascade of carries resulting in a single 1 bit followed by all zeros, that is, a power of two. More fundamentally, we can use a similar trick as yesterday: if , then . Subtracting from this will cancel everything except the at the beginning and the at the end:

But clearly must equal , so in fact . If you know the formula for the sum of a geometric series you can use that as well; the above, slightly generalized, is one way to prove the geometric series formula in the first place.

Now, if we can split a string of 1’s into equal-sized strings of 1’s. But then we can factor out one length- string of 1’s, multiplied by a binary number with a 1 in every p’th place and zeros everywhere else. For example, . (Think about carrying out a multiplication such as in base —it works in exactly the same way.) This is really the same argument as yesterday, just written using binary notation.

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Pingback: MaBloWriMo 5: The Lucas-Lehmer Test | The Math Less Traveled