32
$\begingroup$

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?

$\endgroup$
  • 9
    $\begingroup$ The value of $n$ will in fact always be prime, and therefore odd, except for the single isolated case $n=2$. The proof of this fact is not difficult, but a bit too long for a comment. $\endgroup$ – David Sep 13 '14 at 12:58
  • 6
    $\begingroup$ What about $2^2-1$? $\endgroup$ – illysial Sep 13 '14 at 12:58
  • 8
    $\begingroup$ @Progo Well, $97$ is then special as well. It is the only prime which is divisible by $97$ (being even means being divisible by $2$). $\endgroup$ – Antoine Sep 13 '14 at 18:42
  • 6
    $\begingroup$ @Progo: Well, all prime numbers are odd. The fact that $2$ is the unique even prime makes him quite the odd prime number, I'd say. $\endgroup$ – Asaf Karagila Sep 14 '14 at 4:00
  • 4
    $\begingroup$ @AsafKaragila There's a saying I like, "Two is the oddest prime." $\endgroup$ – Akiva Weinberger Sep 14 '14 at 13:27
77
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for providing proof, it really helps me see why this is true. Sadly, I have to wait three minutes to accept your answer. $\endgroup$ – Progo Sep 13 '14 at 13:06
  • 16
    $\begingroup$ @Progo Don't be sad about having to wait to accept an answer. It's usually best to wait a couple of days anyway, just in case an even better answer is posted. $\endgroup$ – David Richerby Sep 13 '14 at 13:51
  • 3
    $\begingroup$ Man. I which my undergrad textbooks had had proofs as well written as this. +1 good sir; +1. $\endgroup$ – imallett Sep 14 '14 at 7:40
43
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

22 − 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 2n − 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.

$\endgroup$
  • $\begingroup$ Ditto! There's no "if", "else", "or". The answer is ONLY 1! $\endgroup$ – GTodorov Jan 27 '18 at 18:56
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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)$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.