33
$\begingroup$

Is there an easy way of showing that $2^n \pm 1$ is never a perfect power, except for $2^3 + 1 = 3^2 $?

I know that Catalan's conjecture (or Mihăilescu's theorem) gives the result directly, but I'm hopefully for a more elementary method.


I can show that it is never a square, except for $2^3 + 1$.

Proof: Cases $n=1, 2, 3$ are easily dealt with. Henceforth, let $n\geq4$.

$2^n -1 \equiv 3 \pmod{4}$ hence is never a square.

If $2^n +1 =x^2$, then $2^n = (x-1)(x+1)$ and both of these are powers of 2. Thus we must have $(x-1) = 2, (x+1) = 4$. This gives the solution of $2^3 + 1 = 3^2$.


Let's now do an odd prime.

Say $2^n +1 = x^p$. Then $2^n = x^p - 1 = (x-1)(x^{p-1}+x^{p-2} + \ldots +1)$, so both terms are powers of 2. We have $ x = 2^m+1$ is odd. But the other term is the sum of $p$ odd numbers, hence is odd. Since this is clearly greater than 1, we get a contradiction.

Say $2^n -1 = x^p$. Then $2^n = x^p + 1 = (x+1)(x^{p-1} - x^{p-2} + \ldots -x +1 )$, so both terms are powers of 2. We have $x = 2^m -1$ is odd. But the other term is the sum of $p$ odd numbers, hence is odd. Since $x^p + 1 \neq x+1$ except for $p=1$, this means that the term is greater than 1. Hence we get a contradiction.

$\endgroup$
  • 2
    $\begingroup$ Your proof shows that it can never be an even power. Assume now that $2^n \pm 1 =y^{2k+1}$. Then $$2^n=(y \mp 1)(...)$$ Then $y=2^m \pm 1$. Thus $$2^n \pm 1= (2^m \pm 1)^{2k+1} \,.$$ I wonder if we can get a contradiction $\pmod{2^{m+1}}$ or $\pmod{2^{m+2}}$ or something like that. $\endgroup$ – N. S. Sep 21 '13 at 19:49
  • 1
    $\begingroup$ @N.S. Indeed, I just added a way to do cubes, which actually extends to all primes. $\endgroup$ – Calvin Lin Sep 21 '13 at 19:51
  • $\begingroup$ then you are done, primes is all you need. $\endgroup$ – N. S. Sep 21 '13 at 19:53
  • 8
    $\begingroup$ "...$(x-1)(x^2+x+1)$...so both terms are powers of 2..." - but this is impossible: by the left parenthese x must be odd and then the right parenthese is odd $\ne 2^b$ with $b>0$ . Or did I miss something? $\endgroup$ – Gottfried Helms Sep 21 '13 at 20:12
  • 1
    $\begingroup$ @GottfriedHelms That is brilliant! and deals with the primes too. $\endgroup$ – Calvin Lin Sep 21 '13 at 20:16
14
$\begingroup$

(This proof was completed with an insightful comment from Gottfried. I'm placing it as an answer so that it is readily seen that an answer exists, as opposed to just leaving it in the question.)

Suppose we have $ 2^n \pm 1 = x^k$ for some positive integers $x, k$. Cases $n=1, 2, 3$ are easily dealt with. $n=3$ yields the solution $2^3 + 1 = 3^2$. Henceforth, let $n\geq4$. Furthermore, a simple check shows that $x\neq 1, 2$.

First, we will deal with the power $k=2l$ being even. Rewriting $x^{2l}$ as $(x^l)^2$, we may assume that $k=2$.

Proof: $2^n -1 \equiv 3 \pmod{4}$ hence is never a square.

If $2^n +1 =x^2$, then $2^n = (x-1)(x+1)$ and both of these are powers of 2 that differ by 2. Thus we must have $(x-1) = 2, (x+1) = 4$, which gives $2^n = 8$ so $n=3$ (reject). $_\square$

Now, we deal with $k$ odd.

Proof: Say $2^n +1 = x^k$. Then $2^n = x^k - 1 = (x-1)(x^{k-1}+x^{k-2} + \ldots +1)$, so both terms are powers of 2. We have $ x -1$ is a power of 2 greater than 1, hence is even. Thus $x$ is odd. But the other term is the sum of $k$ odd numbers, hence is odd. Since this is clearly greater than 1, we get a contradiction.

Say $2^n -1 = x^k$. Then $2^n = x^k + 1 = (x+1)(x^{k-1} - x^{k-2} + \ldots -x +1 )$, so both terms are powers of 2. We have $x+1$ is a power of 2 that is greater than 1, hence is even. Thus $x$ is odd. But the other term is the sum of $p$ odd numbers, hence is odd. Since $x^p + 1 \neq x+1$ except for $p=1$, this means that the term is greater than 1. Hence we get a contradiction. $ _\square$

$\endgroup$
  • $\begingroup$ Why it has to be closed ?. Give a chance to other to answer from another point of view. This is an open forum. $\endgroup$ – Felix Marin Sep 22 '13 at 22:12
  • $\begingroup$ @FelixMarin Sorry, by 'closed' I meant that it looks like there is an answer, as opposed to being an open unanswered question. I've edited the phrasing for clarity. It was a wrong choice of word, given what close means here. $\endgroup$ – Calvin Lin Sep 22 '13 at 22:12
  • 1
    $\begingroup$ @FelixMarin And certainly, if you can present a clearer / more direct argument, I would be willing to accept your answer. $\endgroup$ – Calvin Lin Sep 22 '13 at 22:16
  • $\begingroup$ 0 k. I am relatively new over here. I understood that 'closed' means "no more answers". Sorry about that. You did a great job. $\endgroup$ – Felix Marin Sep 22 '13 at 22:16
  • $\begingroup$ @FelixMarin The ambiguity is my fault. You can always post more answers to any questions here, unless it has been locked for various reasons (which are rare). In fact, this site encourages you to add insightful answers to old questions which others can learn from. $\endgroup$ – Calvin Lin Sep 22 '13 at 22:18
6
$\begingroup$

We can still generalize your result by elementary means a bit more:

Theorem 1: The only non-trivial solution to $p^k+1=x^n$ for $p\in\mathbb{P},k,x,n \in \mathbb{N}$ are $p,k,x,n=2,3,3,2$.

Proof: We only need to care about $n$ prime. If $n=2$, we would have. $$p^k=(x-1)(x+1)$$ Since both parentheses must be powers of $p$, and since the only powers that are $2$ units apart are $2$ and $4$, we obtain $p=2,k=3,x=3$.

So let's deal now with the odd case: $$p^k=(x-1)(x^{n-1}+x^{n-2}+\cdots+1)$$

Both parentheses must be powers of $p$. If $x=2$, we have already dealt with that case. Else $x$ must be of the form $p^e+1$, but then the first parenthesis would be $p^e$ and the second one would be way greater than $p^e$ and would need to be a power of $p$. That implies that they have $p^e$ as a common factor. But by the residue theorem, $(x-1,x^{n-1}+x^{n-2}+\cdots1)=n$, which is prime. So $e=1$, and $p=n$. So now we have in the second parenthesis: $$(p+1)^{p-1}+(p+1)^{p-2}+\cdots+1=\cdots+\frac{(p-1)p}{2}p+p=p(\cdots+\frac{(p-1)p}{2}+1)$$

Since $2|p-1$, the value inside the parenthesis $\equiv 1 \pmod p$. But that is impossible.

Theorem 2: If there are no solutions to $p^k-1=x^2$, the only non-trivial solution to $p^k-1=x^n$ for $p\in\mathbb{P},k,x,n \in \mathbb{N}$ are $p,k,x,n=3,2,2,3$.

Proof: It is practically the same as the one for the theorem $1$, with the only difference being some signs. But at the end we still arrive at the condratiction of having the second parentheses $\equiv p \pmod {p^2}$, and greater than $p$. If there is any doubt, I can provide details.


Remarks: I attempted to remove the innecesary condition for theorem $2$ but I couldn't, I would be glad to hear suggestions or proofs for doing so. Also, I would like to mention that both theorems work for any prime power $p$. Finally we may note that the Theorem 1 one is just at a composite case of distance to become Mihailescu's theorem. But may the force be with you if you try to do it.

$\endgroup$
1
$\begingroup$

I collected everything you may need about elementary methods solving special cases of Mihailescu theorem here (see cases (iii) and (vii) for this problem)

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