Consider the equation $2^a-2^b=3^c-3^d$ where $a>b>0$, $c>d>0$, and $a,b,c,d$ are all integers. A computer search for solutions with $a,c\le20$ only finds 8-2=9-3, 32-8=27-3, and 256-16=243-3. I would really like there to be only finitely many solutions (even if these 3 aren't the only ones).
I have noted that the lower powers on both sides can be factored out, but since all the exponents are arbitrary, I don't think I can use a pattern in modular residues to get the result.
This feels vaguely reminiscent of Mihăilescu's theorem, but hopefully it's much easier to prove. Can someone point me towards a relevant reference or give me a nudge towards a method for solving it?
Edit:
I've read through Gottfried Helms's explanation, and come to some conclusions, but I'm afraid I'm a bit out of my depth, as I have little experience with Euler's totient theorem (and the related theorem of Carmichael), and no prior experience with Zsigmondy's theorem. I've worked on it a bit, and am presenting my thoughts/current understanding here, in the hopes that people can clarify things for me and bring me closer to a solution.
Firstly, I noticed that there was no good reason to disallow $b=0$ or $d=0$ in the problem, so I started allowing them. Ideally, I would like to produce a complete list of the finitely many tuples (a computer suggests five) of nonnegative integers $\left(a,b,c,d\right)$ with $a>b\ge0,c>d\ge0$ where the above equation holds (note that if we allowed $a=b$ or $c=d$, then we would have $a=b\Leftrightarrow c=d$ and that would be an infinite family of trivial solutions parametrized by $b$ and $d$). Throughout this discussion, I will follow Gottfried Helms in rewriting the equation as $$\frac{2^A-1}{3^d}=\frac{3^C-1}{2^b}\tag{1}$$where $A=a-b,C=c-d>0$, and both sides must be integers.
Quick Observations:
- $2^{b}$ is the highest power of $2$ that divides $3^{C}-1$, as otherwise the left hand side of (1) is odd and the right side is even.
- Thus, $b=0$ is impossible.
- Note that $3^2\equiv1\mod8$, and $3-1\equiv2\mod8$ can't be divisible by $4$. Therefore, $3^{C}-1$ is divisible either by $8$ or by $2$ and not $4$. Hence, by 1., $b=2$ is impossible.
- If $A=1$ then $d=1$ or else the left side of (1) wouldn't be an integer.
- If $C=1$, then $b\le1$ to make the right side of (1) an integer, so $C=1\Rightarrow b=1$ by 2.
Zsigmondy's Theorem
Zsigmondy's Theorem is a deep theorem I has not heard of before Gottfried's post, and it solves many simpler problems of a similar flavor to this one. An good collection of example applications can be found in this issue of the HKUST Mathematical Excalibur. Two relevant corollaries for us are:
- Each entry of the sequence $2^{n}-1$ has a new prime divisor the previous entries didn't except for $n=6$. For example: $2^{2}-1$ has the new prime factor $3$, which $2^{1}-1$ didn't have. $2^{3}-1$ has the new prime factor $7$ which the previous two didn't have. $2^{4}-1$ has the new prime factor $5$, and $2^{5}-1$ has the new prime factor $31$, but $2^{6}-1=3^{2}*7$.
- Each entry of the sequence $3^{n}-1$ has a new prime divisor except for $n=2$. $3^{2}-1$=$\left(3^{1}-1\right)^{3}$, but $3^{3}-1$ has $13$, $3^{4}-1$ has $5$, etc.
More Special Cases:
With Zsigmondy's theorem in hand, we can easily handle some more special cases.
Case: $b=1$ and $d=0$:
In this case, the equation in the problem gives us $2^{a}-2=3^{c}-1$, so that $2^{a}-1=3^{c}$, but $2^{a}-1$ is getting new prime factors other than 3 by Zsigmondy unless $a=0,1,2$. Since $a>b=1$, only $a=2$ is allowed. This yields the solution “4-2=3-1
”.
Case: $C=1$:
By quick observation 5., $b=1$, so we have $2^{A}-1=3^{d}$, which forces $A\le2$ by Zsigmondy. $A=1$ would force $d=0$ and give us the solution from the previous case. If $A=2$, then $d=1$ and we get “8-2=9-3”. (Note, Mihăilescu's theorem could have been used as extreme overkill for this since $2^{A}-1=3^{d}$ is equivalent to $2^{A}-3^{d}=1$.)
Better arguments?
Gottfried seemed to be bringing up Carmichael's strengthening of Euler's totient theorem, but I don't understand how it's being used. The answer made it seem like they were saying something like $a^m\equiv 1\mod n$ for $a=3$ and $n$ coprime to $3$ exactly when $\lambda(n)\mid m$, which is false. $3^3\equiv1\mod13$, for instance. Carmichael's theorem may be very useful here, but I don't understand how to apply it.
I also don't understand how exactly to use Zsigmondy's theorem repeatedly. I can verify Jack Daurizio's comment manually with modular arithmetic, but it seemed like they were using these theorems to quickly make claims about divisibility in a way I couldn't follow.
Any elaboration/explanation on the methods of Gottfried's answer or a different step towards a solution would be much appreciated.
Interesting Corollary
As an aside, I forgot to mention the initial inspiration for this question. I was thinking about pairs of functions $f,g:\mathbb N\to\mathbb N$ such that $(n,m)\mapsto f(n)+g(m)$ is injective. One class of pairs I know is based on interleaving digits, but if the conjecture about powers of 2 and 3 is true, then $f(n)=2^{n+k}$ with $g(m)=3^{m+k}$ would work for some $k$.
Best Answer
I've not enough time to complete that answer at the moment, but I can leave you in a position where you likely can proceed on your own.
The factoring-out is a good start: You get $$ 2^b(2^A-1) = 3^d(3^C-1) $$ Then you rewrite $$ {2^A-1\over 3^d} = {3^C-1 \over 2^b} $$ [lhs]: Then there is a little rule (see "Euler's totient theorem") , which values $A$ must assume for the numerator in the lhs to be divisible by $3$ or more precisely exactly by $3^d$: $$A = \varphi(3^d) = 2 \cdot 3^{d-1} \qquad \text{ by Euler's totient theorem}$$ Sidenote: in this case, we deal with the primefactor $3$ and the $\varphi(3^d)$ is indeed the "order of the cyclic subgroup of $2^n \pmod 3$ - which is relevant here, since we want the exponent $A$ such that the denominator divides exactly. The situation here, with primefactor $3$ is easier than (and different from) some other primefactors like for instance $p=7$ where the $\varphi(7)=6$ but the order of the cyclic subgroup $ \pmod 7$ is smaller and actually $\lambda_7=3$ (Note, this is not the Carmichael-function!) .
One can multiply additional factors to $A$ which only must not contain the primefactor 3: with $v$ where $\gcd(v,3)=1$ the complete expression is $$A = \varphi(3^d) \cdot v = 2 \cdot 3^{d-1} \cdot v \qquad \qquad \gcd(v,3)=1 \tag 1$$
[rhs]: Similarly this is for the rhs: $$ {C = 1 \cdot w \text{ for } b=1 \text{ and } \qquad \qquad \gcd(w,2)=0 \tag {2.1} } $$ $$ C=2^{b-2} \cdot w \text{ for } b \ge 3 \qquad \qquad \gcd(w,2)=0 \tag {2.2}$$ Here a solution for $b=2$ does not exist; because any $3^C-1$ which is divisible by $2^2$ is also divisible by $2^3$ and thus one factor $2$ remains, and then this cannot equal the lhs which has an odd value. In effect, this blows up our equation to $$ {2^{2 \cdot 3^{d-1} \cdot v} - 1\over 3^d} = {3^{1 \cdot w}-1 \over 2^1} \tag {3.1 when $b=1$}$$ $$ {2^{2 \cdot 3^{d-1} \cdot v} - 1\over 3^d} = {3^{2^{b-2} \cdot w}-1 \over 2^b} \tag {3.2 when $b\ge 3$ }$$
I'm not going further at the moment; but now you might look for existence of different additionally primefactors on the lhs and the rhs for choices of $d$ and $b$ and $v$ and $w$. For instance, if $d \gt 1$ we have in the lhs additional primefactors with group-order $3,6,9,18$ which means the primefactors $7,-,73,19$ which must then also occur in the rhs. We know by a theorem of Szigmondy(?spell) that only for $A=2\cdot 3=6$ there is no other additional ("primitive") primefactor existent. This and the "trivial" cases should come out as the only possible solutions.
[update] To make Jack's observation more explicite. First we observe, that in the exponent of the LHS there is unconditionally a factor 2 , so to improve readability a bit we write $$ {4^{ 3^{d-1} \cdot v} - 1\over 3^d} = {3^{2^{b-2} \cdot w}-1 \over 2^b} \tag {3.2}$$
were we took the second version, assuming $b \ge 3$
Then we observe the table of cycle-lengthes for the first few primes for the numerator in the LHS and the RHS:
Now we discuss the possibility of equality, given that $d=2$. Then we look at the composition of $A$, see, what primefactors on the lhs are involved, conclude that they are involved in the rhs (note: must be to the same power!), that sets conditions on $C$ which includes more primefactors for the rhs thus also for the lhs, which then imposes a new composition of A, and so on, until we possibly get a contradiction. Here is a short decision-path-diagram. The "*" sign marks the inclusion of the primefactor due to compositions of $A$ or $C$:
So for the assumption of $d=2$ there is no solution of the original problem