Factors of Mersenne Numbers
It is interesting to consider what numbers might be prime factors of a number of the form Mp=2p-1. It is clear from contruction that two cannot be, but what about three?
Three
If three is a factor of 2n-1, then 2n mod 3 must be one.
| n | 2n mod 3 |
|---|---|
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 1 |
To move one row down the table we need to multiply 2n by two, but the joy of modular arithmetic is that, as we want the answer modulo three, we need only worry about the value of 2n modulo three. So we see that the answer is periodic with a period of two, that one is a possible answer, and that 2n-1 does indeed have a factor of three, provided that n is a multiple of two. But we choose n to be prime, so, save for the case p=2, Mp never has a factor of three.
Five
One can make a similar argument for five.
| n | 2n mod 5 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 3 |
| 4 | 1 |
| 5 | 2 |
So now the period is four, and 2n-1 has a factor of five if n is a multiple of four, which is never the case if n is chosen to be prime. (Given that 2n-1 never has a factor of two, this means that the base-10 representation of 2n-1 always ends with the digit "5" if n is a multiple of four, and hence also that 2n ends with the digit "6" if n is a multiple of four.)
Seven
| n | 2n mod 7 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 1 |
| 4 | 2 |
| 5 | 4 |
| 6 | 1 |
This is more interesting. 2n-1 has a factor of seven if n is a multiple of six, or if n is three more than a multiple of six. But that is simply another way of saying "if n is a multiple of three", so again is excluded if n is prime, save for the case of n=3. And 23-1=7, so is prime.
Nine
Not a prime factor of anything, as it is not a prime.
Eleven to twenty-one
Left as exercises for the reader. The reader might be falling in to the trap of thinking that we are about to show that 2p-1 is always prime, but...
Twenty-three
| n | 2n mod 23 |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 9 |
| 6 | 18 |
| 7 | 13 |
| 8 | 3 |
| 9 | 6 |
| 10 | 12 |
| 11 | 1 |
| 12 | 2 |
The cycle-length is not (23-1), which would be even, and therefore require the n in 2n-1 to be even, and thus not prime. It is instead (23-1)/2, which is odd, eleven. So it requires the n in 2n-1 to be eleven too, as the only prime multiple of eleven.
M11 = 211-1 = 2047 = 23*89
And this is the smallest non-prime Mersenne number for which the exponent is prime.