1

Show that the Diophantine equation $2^n-x^m = 1$ with $x,n,m > 1$ has no solutions.

How do I show that $x^m$ can never be $1$ less than a power of $2$? I tried factoring it but it doesn't seem like I can.

user19405892
  • 15,592
  • It is pretty easy to see that $2^n- 1= 1+ 2+ 4+ \cdot\cdot\cdot+ 2^{n-1}$. Can you show that that is never a power of a single integer? – user247327 Dec 04 '15 at 16:25
  • We have to show that there exist no $x,m$ such that $x^m = 1+2+4+\cdots+2^{n-1}$. I need a hint. – user19405892 Dec 04 '15 at 16:35

1 Answers1

1

Hint: It is clear that $x$ must be odd. Thus, if $m$ is even, $x^{m}$ is of the form $8k+1$, and therefore the highest power of $2$ that divides $x^m+1$ is $2^1$. So $m$ must odd.

Now factoring works. We have $x^m+1=(x+1)(x^{m-1}-x^{m-2}+x^{m-3}-\cdots +1)$. Note that the second term on the right has an odd number of odd terms. There are only a couple of steps left to the end.

Remark: Catalan long ago conjectured that if $x,y,m,n$ are integers $\ge 2$, the equation $x^m-y^n=1$ only holds when $x=3$, $m=2$, $y=2$, and $n=3$. This conjecture was proved not many years ago by Mihailescu.

André Nicolas
  • 507,029
  • How if $m$ is even $x^m$ is of the form $8k+1$? – user19405892 Dec 04 '15 at 16:43
  • If $m$ is even, then $x^m$ is a perfect square. Any odd square is of the shape $8k+1$ (for our purposes $4k+1$ would be good enough.) For $(2w+1)^2=4w^2+4w+1=4(w)(w+1)+1$, and one of $w$ or $w+1$ is even. – André Nicolas Dec 04 '15 at 16:46
  • Just curious, how would you get that any odd square is of the form $8k+1$? – user19405892 Dec 04 '15 at 16:48
  • Also how do you know that any power odd square is of the form $4k+1$ just from $(2w+1)^2$? – user19405892 Dec 04 '15 at 16:52
  • We expand, get $4(w^2+w)+1$. Let $k=w^2+w$. – André Nicolas Dec 04 '15 at 16:55
  • Yes, but any square. Then we square $4k+1$? Etc.? – user19405892 Dec 04 '15 at 17:00
  • No we don't, we are finished. Any odd number is of the form $2w+1$ for some integer $w$. The square of this general odd number is $4(w^2+w)+1$, so is of the form $4k+1$. Maybe you are familiar with congruences. I have shown in the comments that if $z$ is an odd integer, then $z^2\equiv 1\pmod{4}$, indeed that $z^2\equiv 1\pmod{8}$. – André Nicolas Dec 04 '15 at 17:03
  • Ah. That makes much more sense. But why must $k$ be even? – user19405892 Dec 04 '15 at 17:05
  • In the comment above? I have already covered that. Recall that $k=w^2+w=w(w+1)$. One of $w$ or $w+1$ is even for any $w$, so their product is even. But for the solution of the question, all we need is that if $x$ is odd and $m$ is even, then $x^m$ is of the form $4k+1$. For then $x^m+1=4k+2=2(2k+1)$, twice an odd number, and therefore in particular not of shape $2^n$ for $n\ge 2$. – André Nicolas Dec 04 '15 at 17:10
  • I think to end we should also add that $x^{m-1}-x^{m-2}+x^{m-3}-\cdots+1 > 1$ so that it can't be a power of $2$. – user19405892 Dec 04 '15 at 17:26
  • That's right. I left that step for you to find. – André Nicolas Dec 04 '15 at 17:28