# Are there integer solutions to $9^x - 8^y = 1$?

This came up in proving non-regularity of a certain language (powers of 2 over the ternary alphabet). Any clue to the above equation could help me move forward.

Edit: Of course, $x = 1, y = 1$ is a solution. I am looking for non-trivial solutions.

-
yes x=1,y=1 is a soution – anonymous Oct 8 '10 at 16:11
Thanks Chandru1, I edited it. – user813 Oct 8 '10 at 16:22
@avinash: out of curiosity, how does this come up in proving non-regularity of the language you describe? The approach which first occurs to me is totally different. Are you using the pumping lemma? – Qiaochu Yuan Oct 8 '10 at 21:14
@Qiaochu: Yes, I was trying pumping lemma. But it's going nowhere. How did you solve it? – user813 Oct 9 '10 at 3:48
@avinash: the approach I thought of is unnecessarily complicated. There is a theorem of Berstel which implies that if the language you're looking at is regular, then the number L_n of words of length n must be eventually periodic, and I believe one derives a contradiction from here. – Qiaochu Yuan Oct 9 '10 at 9:43

Except $x=1$ and $y=1$ there aren't any.

We have that

$$3^{2x} - 1 = 8^y$$

i.e

$$(3^x + 1)(3^x - 1) = 8^y$$

Thus we must have that

$$3^x + 1 = 2^m, 3^x - 1 = 2^n$$

Thus $$2^m - 2^n = 2$$

i.e $$2^n(2^{m-n} - 1) = 2$$

Thus $n=1$ and $m=2$.

-
You didn't use the assumption that x>1; you got n=1 which implies x=1. :-) (Many times a proof by contradiction can be simplified if you try to rewrite it without the contradication… it's usually worth a shot to see if it gets simpler.) – ShreevatsaR Oct 8 '10 at 16:58
@Shree: Right, I will just delete that line. – Aryabhata Oct 8 '10 at 17:07
@Moron, pardon my ignorance, but can you explain why it must be true that $3^x+1=2^m$ and $3^x-1=2^n$? – user1736 Oct 8 '10 at 17:18
@user: If A*B = a power of 2 = 2^y, then, both must be powers of 2. (I am counting 1 to be a power of 2 = 2^0). This is because any prime that divides A, must divide 2^y and hence must be 2. – Aryabhata Oct 8 '10 at 17:22
@Moron: This is so elementary and beautiful. Thanks. – user813 Oct 8 '10 at 17:44

The only solution is $x=y=1$. This is a special case of Catalan's conjecture which was proven by Mihailescu in 2002: the only solution in natural numbers of $x^a - y^b = 1$ with $a,b\gt 1$ is $x=3$, $a=2$, $y=2$, and $b=3$.

But as Moron points out, it can be deduced much more elementarily.

-

Equation $\rm\ 3^{2x}-2^{3y}=1\$ is an instance of various special cases of Catalan's Conjecture.

First,$\$ making the specialization $\rm\ \ \: z,\:p^n = 3^x,2^{3y}\$ below yields $\rm\ x = 1 = y\$ as desired.

LEMMA$\ \$ $\rm z^2 - p^n = 1\ \ \Rightarrow\ \ z,\:p^n = \:3\ ,\:2^3\$ or $\ 2,\:3\$ for $\rm\ \ z,\:p\:,n\in \mathbb N,\ \ p\:$ prime

Proof $\rm\ \ \ (z+1)\:(z-1)\: =\: p^n\ \ \Rightarrow\ \ z+1 = p^{\:j},\ \ z-1 = p^k\$ for some $\rm\ j,\:k\in \mathbb N$

$\rm\quad \:\Rightarrow\ \ \ \ 2\ =\ p^{\:j} - p^k\ =\ p^k\: (p^{\:j-k}-1) \ \Rightarrow\ p^k=2\$ or $\rm\ p^k = 1 \ \Rightarrow\ \ldots$

Second, it's simply the special case $\rm\: X = 3^x,\ Y = 2^y\:$ of $\rm\ X^2 - Y^3 = 1\:,\:$ solved by Euler in 1738. Nowadays one can present this solution quite easily using elementary properties of $\rm\ \mathbb Z[\sqrt[3]{2}]\:$, e.g see p.44 of Metsankyla: Catalan's Conjecture: another old diophantine problem solved. See also this MO thread and this MO thread and Schoof: Catalan's Conjecture. Note also that Catalan equations are a special case of the theory of generalized Fermat (FLT) equations, e.g. see Darmon's exposition.

-