MaBloWriMo 3: Mersenne composites in binary

Yesterday we saw that $M_{pq} = 2^{pq} - 1$ must be composite, since

$2^{pq} - 1 = (2^p - 1)(2^{p(q-1)} + 2^{p(q-2)} + 2^{p(q-3)} + \dots + 2^p + 1)$ .

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 $2$ to denote a number written in base 2. For example, $1011011_2 = 1 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 64 + 16 + 8 + 2 + 1 = 91_{10}.$

How are Mersenne numbers $M_n = 2^n - 1$ written in binary? In fact, they are written $M_n = 111\dots111_2$ , with $n$ 1 bits. For example, $M_4 = 15$ is written in base 2 as $1111_2 = 2^3 + 2^2 + 2^1 + 2^0$ . There are a couple ways to see this. First, if you know something about how base-2 arithmetic works, note that adding $1$ to a binary number consisting of all $1$ ’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 $S = 2^{n-1} + 2^{n-2} + \dots + 2^1 + 2^0$ , then $2S = 2^n + 2^{n-1} + \dots + 2^2 + 2^1$ . Subtracting $S$ from this will cancel everything except the $2^n$ at the beginning and the $-2^0$ at the end:

$\begin{array}{ccccccccc} 2^n &+& 2^{n-1} &+& \dots &+& 2^1 && \\ &-& 2^{n-1} &-& \dots &-& 2^1 &-& 2^0 \\ \hline 2^n &&&&&&&-& 1 \end{array}$

But clearly $2S - S$ must equal $S$ , so in fact $S = 2^n - 1$ . 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 $n = pq$ we can split a string of $n$ 1’s into $q$ equal-sized strings of $p$ 1’s. But then we can factor out one length- $p$ string of 1’s, multiplied by a binary number with a 1 in every p’th place and zeros everywhere else. For example, $111\,111\,111\,111_2 = 111_2 \times 1\,001\,001\,001_2$ . (Think about carrying out a multiplication such as $354 \times 100100100100 = 354354354354$ in base $10$ —it works in exactly the same way.) This is really the same argument as yesterday, just written using binary notation.