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