Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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
show 1 more comment

3 Answers 3

up vote 41 down vote accepted

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

share|improve this answer
    
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
4  
@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
2  
@Moron: This is so elementary and beautiful. Thanks. –  user813 Oct 8 '10 at 17:44
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.