Are Mersenne prime exponents always odd?

Question

I have been researching Mersenne primes so I can write a program that finds them. A Mersenne prime looks like $2^n-1$. When calculating them, I have noticed that the $n$ value always appears to be odd. Is there confirmation or proof of this being true?

Answer 1

Theorem. If $2^n-1$ is prime then $n$ is prime.

Proof. Suppose that $2^n-1$ is prime, and write $n=st$ where $s,t$ are positive integers. Since $$x^s-1=(x-1)(x^{s-1}+x^{s-2}+\cdots+1)\ ,$$ we can substitute $x=2^t$ to see that $2^t-1$ is a factor of $2^n-1$. Since $2^n-1$ is prime there are only two possibilities, $$2^t-1=1\quad\hbox{or}\quad 2^t-1=2^n-1\ .$$ Therefore $t=1$ or $t=n$. We have shown that the only possible factorisations of $n$ are $n\times1$ and $1\times n$. Hence, $n$ is prime.

Comment. If $n$ is prime it is not always true that $2^n-1$ is prime. For example, $2^{11}-1=23\times89$.

Answer 2

Note that for $m\ge 2$ $$2^{2m}-1=(2^m)^2-1=(2^m-1)(2^m+1)$$ is not a prime number.

Answer 3

Yes, the formula $2^n-1$ may only yield a prime if $n$ is prime, therefore the only even value of $n$ which yields a prime is $2$, which yields the Mersenne prime $2^2-1=3$. However for some prime values of $n$ the result is not prime, for example $2^{11}-1=23\cdot 89$.

In general $a^x-1$ is composite if $x$ is composite. This can be seen very easily by writing out the numbers in the base $a$. The number will have $x$ digits, and where $x$ is composite, possible factorisations involving $a^y-1$ (where $y$ is a factor of $x$) become obvious.

$2^4-1$ in binary is $1111$ which can be factored as $101\cdot 11$

$2^{15}-1$ in binary is $111 111 111 111 111$ which can be factored as $1001001001001 \cdot 111$ or $10000100001 \cdot 11111$

---

$10^8-1$ is $99999999$ in decimal which can be factored as $1010101 \cdot 99$ or $10001 \cdot 9999$. For $a$ greater than $2$ we can also separate out the factor $a-1$ (in this case, $9$): $9 \cdot 1010101 \cdot 11$ or $9 \cdot 10001 \cdot 1111$

As an aside, the presence of $a-1$ as a factor means that all $a^x-1$ with $a>2$ and $x>1$ are composite.

Answer 4

Sorry everyone, but the question clearly states if Mersenne prime powers are always odd.

2² − 1 is a Mersennse prime which power is 2 which is an even number.

Therefore the only possible answer is no.

The only thing we can be certain is that if 2ⁿ − 1 is prime, then n is prime as it has been proved in other answers.

It just happens that 2 is the only even prime number.

Answer 5

Yes, if $n$ is positive and even, then one can factor into integers:

$$2^n - 1 = (2^{n / 2} + 1)(2 ^ {n / 2} - 1).$$

Thus in this case $2^n - 1$ is composite if $2^{n / 2} - 1 > 1$, that is, if $n > 2$.

Answer 6

If $n$ is composite then $n=ab$, where $a\ne n$, $b\ne n$. So: $$ 2^{ab}-1 = (2^a)^b -1 = (2^a-1)(1+ 2^a + 2^{2a} + \ldots + 2^{a(b-1)}) $$

So $(2^{a}-1)$ divides $(2^{n}-1)$

Answer 7

If $n=2k$ then we can show that $3|(4^k-1)$ by induction. When $k=1$, $3|3$ and we are done. Suppose $ 3|(4^m-1)$. Note that $$4^{m+1}-1=4(4^m-1)+3.$$ Which is divisible by $3$ by the induction hypothesis and the fact that $3|3$.

So $2^{2k}-1$ is not prime when $k>1$.

Alternatively: $4^n-1=(4-1)(4^{n-1}+...+1)$ (used David's idea here).

Answer 8

There is an extremely simple proof of this fact if you simply write the number in binary and realize that $2^n - 1$ is written as $n$ $1$'s. If $n$ is a composite number (i.e. non prime) then it can be grouped into a subset of $1$'s. Here's an example, $2^{10} - 1$:

\begin{align} 2^{10} - 1 =&\ 1111111111_2 = 1023 \\=&\ 1111100000_2 + 0000011111_2 \\ =&\ (2^5 - 1)*2^5 + (2^5 - 1)\\ =&\ 31*2^5 + 31 \\ =&\ 31(2^5 + 1)\\ =&\ 31 * 33 \end{align}

or

\begin{align} 2^{10} - 1 =&\ 1111111111_2 = 1023 \\=&\ 1100000000_2 + 0011000000_2 + 0000110000_2 + 0000001100_2 + 0000000011_2 \\ =&\ 3*2^8 + 3*2^6 + 3*2^4 + 3*2^2 + 3*2^0 = 1023\\ =&\ 3*(2^8 + 2^6 + 2^4 + 2^2 + 2^0) = 1023 \\ =&\ 3*341 = 1023 \end{align}

If $n$ is composite (i.e. non-prime) then the $1$'s can be grouped into sets which will make $2^n - 1$ non-prime. Basically, assume that $n$ is non-prime such that $n = \alpha \beta$, then $2^n - 1$ will be divisible by $2^\alpha - 1$ and $2^\beta - 1$.

It's worth pointing out that (obviously) $n$ prime isn't enough--because all we've proved is that "if $n$ isn't prime $2^n - 1$ definitely isn't" (I just showed how to find a factor for any $2^n - 1$ where $n$ isn't prime). And you probably already realize things like $2^{11} - 1$ exist where that's not a prime number (also definitely not divisible by $11$ btw) and thus not a Mersenne's Prime.

A couple of quick examples:

\begin{align*} 2^4 - 1 &\ \leadsto 4 = 2*2 \leadsto 2^4 - 1 \text{ is divisible by } 2^2 - 1 = 3& 15 =&\ 3*5 \\ 2^{12} - 1 &\ \leadsto 12 = 4*3 \leadsto 2^4 - 1 = 15 \text{ and } 2^3 - 1 = 7 & 4095 =&\ 7*582, 15*273\end{align*}

Super Late Edit

I realize now the question was, "does the exponent always have to be odd"? Well I guess I didn't answer that--I showed that the exponent always has to be prime which implies it's virtually always odd--always unless $2^2 - 1$ is a Mersenne prime, which it is, so that's your one and only counterexample.

p.s. Also I always find it a little silly to say something like "$2$ is the only even Mersenne exponent". That would be like saying "$3$ is the only Mersenne exponent divisible by $3$"...of course we could say something like "no Mersenne exponent is divisible by $11$"!