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.