11
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Exactly right. Similarly if $2^n+1$ is prime then $n$ is a power of two. $\endgroup$ – anon Mar 4 '13 at 0:00
  • 4
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Mar 4 '13 at 0:19
  • $\begingroup$ 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$). $\endgroup$ – Marc van Leeuwen Sep 17 '13 at 11:41
  • $\begingroup$ 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$. $\endgroup$ – Andreas Caranti Sep 17 '13 at 11:42
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Sep 17 '13 at 11:44
9
$\begingroup$

I'll try to recapituate all the comments made in an adapted version of the proof.

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Should I say that $x$ and $y$ have to be greater then $1$ then? $\endgroup$ – user64013 Mar 4 '13 at 0:11
  • $\begingroup$ yes, and you are also implicitly assuming $n\gt1$ $\endgroup$ – newToProgramming Mar 4 '13 at 0:15
  • $\begingroup$ Whats the reasoning x and y cant be 1? $\endgroup$ – user64013 Mar 4 '13 at 3:06
  • $\begingroup$ 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? $\endgroup$ – newToProgramming Mar 4 '13 at 3:16

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.