MaBloWriMo: Mersenne composites

The name of the game is to find Mersenne numbers M_n = 2^n - 1 which are also prime. Today, a simple observation: M_n = 2^n - 1 can only be prime when n is also prime. Put conversely, if n is composite then M_n is also composite. For example, 4 is composite and M_4 = 2^4 - 1 = 15 is also composite; M_6 = 2^6 - 1 = 63 is composite; and so on.

Why is this? We can actually give a very explicit proof that simply shows how to factor M_n when n is composite: if n = pq, then

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

Can you see why? Multiplying 2^p by 2^{p(q-1)} + 2^{p(q-2)} + \dots + 1 yields 2^{pq} + 2^{p(q-1)} + \dots + 2^p. If we then subtract 2^{p(q-1)} + 2^{p(q-2)} + \dots + 2^p + 1, everything cancels except the first 2^{pq} and the last -1.

\begin{array}{ccccccccccc} 2^{pq} &+& 2^{p(q-1)} &+& 2^{p(q-2)} &+& \dots &+& 2^p && \\ &-& 2^{p(q-1)} &-& 2^{p(q-2)} &-& \dots &-& 2^p &-& 1 \\ \hline 2^{pq} &&&&&&&&&-& 1 \end{array}

So in fact, we can see that M_{pq} must be evenly divisible by M_p; because pq = qp, it must be evenly divisible by M_q as well. So, for example, M_4 = 15 = 3 \cdot 5 is divisible by M_2 = 3; M_6 = 63 = 7 \cdot 3^2 is divisible by M_3 = 7 and M_2; M_{10} = 1023 = 3 \cdot 11 \cdot 31 is divisible by M_5 = 31 and M_2.

There is also a nice way to think of this in terms of binary numbers; I’ll explain that tomorrow.

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: Mersenne composites

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

Comments are closed.