# If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.

I understand the idea of the proof. I just want to make sure I wrote my proof well.

Suppose $n$ is not prime. Then $\exists x,y \in \mathbb{Z}$ such that $n = xy$.

$2^{xy} - 1 = (2^x)^y - 1$

$= (2^y - 1)(2^{y(x-1)} + 2^{y(x-2)} + ... + 2^{y} + 1)$

Since $2^{n} - 1$ is divisible by $2^y - 1$ it must be that $2^n - 1$ is not prime. Contradiction. Thus $n$ must be prime.

How does this look?

• Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two. – anon Mar 4 '13 at 0:00
• Don't say in $\mathbb{Z}$, that include $(-2)(-3)=6$. And it is positive integer. And in principle you must take care of the non-prime $n=1$. And you must insist that $x$ and $y$ are $\gt 1$. – André Nicolas Mar 4 '13 at 0:19
• Formally, you also need to say a word about $n=1$ (which does not satisfy the hypothesis, but since you are going by contrapositive and $n=1$ does satisfy the hypothesis of the contrapositive, namely $n$ is not prime, you need to dismiss the case (by saying $2^1-1$ is not prime) before introducing $x,y$). – Marc van Leeuwen Sep 17 '13 at 11:41
• To make the proof really complete, you have to assume $x, y > 1$, so that $2^{y} - 1 > 1$, and $2^{y} - 1$ is a proper divisor of $2^{n} - 1$. – Andreas Caranti Sep 17 '13 at 11:42
• @AndreasCaranti: and $2^{y(x-1)} + 2^{y(x-2)} + ... + 2^{y} + 1>1$ (since $x>1$) so the other factor is also a proper divisor. – Marc van Leeuwen Sep 17 '13 at 11:44

If $2^n−1$ is prime from some integer$~n$, then $n$ must also be prime.

Since the hypothesis requires $n\geq2$ to be true, one may assume that. We prove the contrapositive: if $n\geq2$ is not prime then $2^n-1$ is not prime either.

Suppose $n\geq2$ is not prime. Then there exist integers $x,y>1$ such that $n = xy$.

One has $2^n-1 = 2^{yx} - 1 = (2^y)^x - 1 = (2^y - 1)(2^{y(x-1)} + 2^{y(x-2)} + \cdots + 2^{y.1} + 2^{y.0})$. Since $y>1$ the first factor $2^y - 1$ is${}>1$, and since $x>1$ that factor is less than $2^n-1$.

Since $2^n - 1$ has a proper divisor $2^y - 1$ greater than$~1$, we have shown that $2^n - 1$ is composite, establishing the contrapositive.

Remark. The contrapositive statement proved remains true if powers of $2$ are replaced throughout by powers of some integer $a\geq2$. However with that change it is no longer true that the original hypothesis requires $n\geq2$, as $n=1$ might work. Therefore such a generalisation of the original statement requires an explicit additional hypothesis $n\geq2$.

Perhaps a minor nit-pick, but it seems the middle step should be $((2^y)^x-1)$, since you're utilizing the identity $$a^x-1=(a-1)(a^{x-1}+a^{x-2}+\cdots+a+1)$$ with $a=2^y$.

This feels more like proof by contrapositive than proof by contradiction. Also, although obvious, without conditions on n,x,y it is not clear that $2^y-1$ can't be 1.

• Should I say that $x$ and $y$ have to be greater then $1$ then? – user64013 Mar 4 '13 at 0:11
• yes, and you are also implicitly assuming $n\gt1$ – newToProgramming Mar 4 '13 at 0:15
• Whats the reasoning x and y cant be 1? – user64013 Mar 4 '13 at 3:06
• In your proof, you state $2^n-1$ is divisible by $2^y-1$ and use this to conclude that $2^n-1$ is not prime, however consider what happens if $y$ is 1, can you still justify that same conclusion? – newToProgramming Mar 4 '13 at 3:16