# Factors of Mersenne Numbers

It is interesting to consider what numbers might be prime factors
of a number of the form M_{p}=2^{p}-1. It is clear
from contruction that two cannot be, but what about three?

### Three

If three is a factor of 2^{n}-1, then
2^{n} mod 3 must be one.

n | 2^{n} mod 3 |
---|---|

1 | 2 |

2 | 1 |

3 | 2 |

4 | 1 |

To move one row down the table we need to multiply 2^{n} 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
2^{n} modulo three. So we see that the answer is periodic
with a period of two, that one is a possible answer, and that
2^{n}-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, M_{p} never has a factor of three.

### Five

One can make a similar argument for five.

n | 2^{n} mod 5 |
---|---|

1 | 2 |

2 | 4 |

3 | 3 |

4 | 1 |

5 | 2 |

So now the period is four, and 2^{n}-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 2^{n}-1 never has a factor of two,
this means that the base-10 representation of 2^{n}-1 always
ends with the digit "5" if n is a multiple of four, and hence also
that 2^{n} ends with the digit "6" if n is a multiple of four.)

### Seven

n | 2^{n} mod 7 |
---|---|

1 | 2 |

2 | 4 |

3 | 1 |

4 | 2 |

5 | 4 |

6 | 1 |

This is more interesting. 2^{n}-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 2^{3}-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 2^{p}-1
is always prime, but...

### Twenty-three

n | 2^{n} 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 2^{n}-1 to be even, and thus not prime. It
is instead (23-1)/2, which is odd, eleven. So it requires the n in
2^{n}-1 to be eleven too, as the only prime multiple of
eleven.

M_{11} = 2^{11}-1 = 2047 = 23*89

And this is the smallest non-prime Mersenne number for which the exponent is prime.