Consider the equation $$|2^x-3^y|=1$$ in the unknowns $x \in \mathbb{N}$ and $y \in \mathbb{N}$. Is it possible to prove that the only solutions are $(1,1)$, $(2,1)$ and $(3,2)$?


Yes. Levi ben Gerson (1288-1344), also known as Gersonides, proved this. The Gersonides proof can be found here.

EDIT: miracle notes that the link is broken. This link works (for now). But to keep everyone happy, I'll paste in the relevant parts of what's there:

In 1342, Levi ben Gerson, also known as Gersonides (1288-1344), proved that the original four pairs of harmonic numbers are the only ones that differ by 1. Here's how his proof went (using modern notation). [note --- "harmonic numbers" are those that can be written as $2^n3^m$]

If two harmonic numbers differ by 1, one must be odd and the other even. The only odd numbers are powers of 3. Hence one of the two harmonic numbers must be a power of 3 and the other a power of 2. The task then involves solving two equations:

$2^n = 3^m + 1$ and $2^n = 3^m - 1$.

Gersonides had the idea of looking at remainders after division of powers of 3 by 8 and powers of 2 by 8. For example, 27 divided by 8 gives a remainder of 3. For powers of 3, the remainders all turn out to be 1 or 3, depending on whether the power is even or odd. The remainders for powers of 2 are 1, 2, 4, then 0 for all powers higher than 2.

For $2^n = 3^m + 1$, when $m$ is odd, $3^m$ has remainder 3, and $2^n = 3^m + 1$ must then have the remainder 4, so $n = 2$ and $m = 1$. That gives the consecutive harmonic numbers 3, 4. When $m$ is odd, the equation gives the consecutive harmonic numbers 1, 2.

For $2^n = 3^m - 1$, when $m$ is odd, $3^m$ has remainder 3, so $2^n = 3^m - 1$ has remainder 2; as a result, $n = 1$ and $m = 1$, to give the consecutive harmonic numbers 2, 3. The final case, when $m$ is even, is a little trickier and requires substituting $2k$ for $m$, then solving the equation $2^n = 3^{2k} - 1 = (3^k - 1)(3^k + 1)$. That gives the consecutive harmonic numbers 8, 9. QED.

  • 2
    $\begingroup$ Ah, number theory is always amazing! $\endgroup$ – Siminore Jun 30 '12 at 10:52
  • 1
    $\begingroup$ the link is broken. answers that are barely more than a link to an external site are not apreciated in this forum. $\endgroup$ – miracle173 Sep 3 '13 at 6:54
  • $\begingroup$ The answer got 7 upvotes and a tick, so I guess it was appreciated [note spelling] by at least a few people in this forum. But I take your point, @miracle. $\endgroup$ – Gerry Myerson Sep 3 '13 at 12:17

This is an easy consequence of Catalan's conjecture, which was famously proved by Preda Mihăilescu in 2002 (so now it's also called Mihăilescu's theorem):

$3^2-2^3=1$ is the only solution to $x^a - y^b = 1$ for integers $a, b, x, y \ge 2$.

  • 4
    $\begingroup$ True, but that is killing a fly with an atom bomb. $\endgroup$ – Gerry Myerson Jun 30 '12 at 11:01
  • 3
    $\begingroup$ That's going too far, Gerry! I'm using a sledgehammer to crack a nut, is all. $\endgroup$ – TonyK Jun 30 '12 at 11:02

Assume that $x>3$ and $y>2$.

$3^2=1\pmod{8}$. Since $3\not=-1\pmod{8}$ we know that $3^y\not=-1\pmod{8}$. Thus, if $|2^x-3^y|=1$, we must have $2^x-3^y=-1$ and $y$ must be even. Thus, we get that $$ 2^x=(3^{y/2}-1)(3^{y/2}+1)\tag{1} $$ The only factors of a power of $2$ are other powers of $2$, and the only powers of two that differ by $2$ are $2$ and $4$, but since $y>2$, we have $3^{y/2}-1>2$ and $3^{y/2}+1>4$.

Therefore, there are no $x>3$ and $y>2$ so that $|2^x-3^y|=1$.

  • $\begingroup$ Wow this proof looks even better than the Levi's one :O $\endgroup$ – Andrius Naruševičius Jun 30 '12 at 20:03
  • $\begingroup$ @AndriusNaruševičius: I just saw the link in Gerry's answer (since you mentioned it). It seems to be the same idea, just reorganized a bit. I did what I thought was the hard case, because the other cases seem almost trivial. $\endgroup$ – robjohn Jun 30 '12 at 20:42
  • $\begingroup$ Still looks more understandable to an average person :) $\endgroup$ – Andrius Naruševičius Jul 1 '12 at 6:50

Case 1: If $2^x=3^y+1$ then $x \ge 1$. If $y=0$ then $x=1$. If $y \ge 1$ then $3^y+1 \equiv 1 \pmod{3}$. Therefore $2^x \equiv 1 \pmod{3}$. Hence $x=2x_1$ with $x_1 \in \mathbb{N}^*$. The equation is equivalent to $$3^y= (2^{x_1}-1)(2^{x_1}+1)$$ Since $2^{x_1}+1>2^{x_1}-1$ and $\gcd (2^{x_1}-1,2^{x_1}+1) \ne 3$ then $2= 3^{m} (3^{n-m}-1)$ with $2^{x_1}-1=3^m,2^{x_1}+1=3^n$. Thus, $m=0,n=1$. We obtain $x_1=1$ or $x=2$. Thus, $y=1$.

Case 2. If $3^y=2^x+1$. If $x=0$ then there is no natural number $y$. If $x=1$ then $y=1$. If $x \ge 2$ then $3^y \equiv 1 \pmod{4}$. Thus, $y$ is even, let $y=2y_1$ with $y_1 \in \mathbb{N}^*$. The equation is equivalent to $$2^y=(3^{y_1}-1)(3^{y_1}+1)$$ Thus, $2=2^n(2^{m-n}-1)$ with $2^m=3^{y_1}+1,2^n=3^{y_1}-1$. It follows that $n=1,m=2$. Thus, $y_1=1$ or $y=2$. We get $x=3$.

The answer is $\boxed{ (x,y)=(1,0),(1,1),(2,1),(3,2)}$.


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.