The name of the game is to find Mersenne numbers which are also prime. Today, a simple observation: can only be prime when is also prime. Put conversely, if is composite then is also composite. For example, is composite and is also composite; is composite; and so on.

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

Can you see why? Multiplying by yields . If we then subtract , everything cancels except the first and the last .

So in fact, we can see that must be evenly divisible by ; because , it must be evenly divisible by as well. So, for example, is divisible by ; is divisible by and ; is divisible by and .

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

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