# 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.

n2n mod 3
12
21
32
41

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.

n2n mod 5
12
24
33
41
52

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

n2n mod 7
12
24
31
42
54
61

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

n2n mod 23
12
24
38
416
59
618
713
83
96
1012
111
122

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.