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.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, arithmetic, computation, famous numbers, iteration, modular arithmetic, number theory, primes and tagged , , , , , , . Bookmark the permalink.

One Response to MaBloWriMo 3: Mersenne composites in binary

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

Comments are closed.