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?


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:

  1. $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.
  2. Thus, $b=0$ is impossible.
  3. 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.
  4. If $A=1$ then $d=1$ or else the left side of (1) wouldn't be an integer.
  5. 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:

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

  • 1
    $\begingroup$ My "divisibility chain" goes this way: assuming $d>1$, we have (with Gottfried notation) $6|A$, so $7|(2^A-1)$. This gives $7|(3^C-1)$, and since the order of $3\pmod{7}$ is $6$, $6|C$. This implies $(3^6-1)|(3^C-1)$, but in $(3^6-1)$ a new (Zsigmondy's) prime factor appears, $13$. So we have $13|3^C-1$, then $13|2^A-1$. Since the order of $2\pmod{13}$ is twelve, we have $12|A$, and the "divisibility chain" has begun - we can say $5|(2^{12}-1)|(2^A-1)$, so $5|3^C-1$, so $4|C\ldots$ - if we prove that a new prime pops up at each step, we are done. $\endgroup$ – Jack D'Aurizio Nov 1 '13 at 10:32
  • 1
    $\begingroup$ Just two more short comments. 1) Carmichael-function: no, I did not use the Carmichael function - just the order of the cycles in $2^n - 1 \pmod p$ for some fixed primefactor $p$ when $n$ gets increased. That cycle-lengthes define then the exponents in the numerators in (1) depending on the exponents in the denominators in the way I've indicated in my answer. 2) Zsygmondi: The focus by his theorem is that if $2^p-1$ has some primefactors, and $2^q-1$ has some other primefactors, then $2^{pq}-1$ has that primefactors, but also additionally ones - except if $pq=6$. Analoguously for $3^n-1$ $\endgroup$ – Gottfried Helms Nov 3 '13 at 21:29
  • 1
    $\begingroup$ A newer discussion with a bit more explicite material (in the same spirit as the approaches here) can be found in: math.stackexchange.com/questions/1946621/… $\endgroup$ – Gottfried Helms Oct 14 '16 at 11:34

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:

  pf   4^A-1  3^C-1
    2    -    1
    3    1    -
    5    2    4
    7    3    6
   11    5    5
   13    6    3
   17    4   16
   19    9   18
   23   11   11
   29   14   28
   31    5   30
   37   18   18
   41   10    8
   43    7   42
   47   23   23
   53   26   52
   59   29   29
   61   30   10
   67   33   22
   71   35   35
   73    9   12 
 ...    ...  ...

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

 *   3   1    0
 *   7   3    6 ==> C=2.3.w
 *  13   6    3 ==> A=2.3
 *   5   2    4 ==> C=4.3.w
 * 73    9   12 ==> A=2.3^2  #####
contradiction, because exponent of 3 in A was assumed=1

So for the assumption of $d=2$ there is no solution of the original problem

  • $\begingroup$ Assuming $d>1$, a nice game starts. You have $7|(2^A-1)$, so $6|C$. This gives $13|(3^C-1)$, so $12|A$. This gives $5|(2^A-1)$, so $4|C$, then $12|C$. This gives $73|(3^C-1)$, so $9|A$, then $36|A$. This gives $19|(2^A-1)$, so $18|C$, then $36|C$. This gives $757|(3^C-1)$, so $756=2^2\cdot 3^3\cdot 7$ divides $A$. This gives that a lot of new primes divide $(3^C-1)$. Can we prove that the game never ends? $\endgroup$ – Jack D'Aurizio Oct 18 '13 at 7:25
  • $\begingroup$ @Jack: I think so, because the Szigmondy-theorem says, that there are always "primitive" primefactors dividing $2^A-1$ resp $3^C-1$ if we compose A and C by any new factor. Another proof which I would attempt is to find a primefactor which creates a contradiction. Candidates are such, which have the same cyclic order for $2^A-1$ and $3^C-1$; the $A$ must be a multiple of $C$ and this requires more factors in ${2^{k C}-1\over 3^d}$ than in ${3^C-1 \over 2^b}$. Unfortunately I've at the moment not enough time to dig into this... $\endgroup$ – Gottfried Helms Oct 18 '13 at 8:08
  • $\begingroup$ @JackD'Aurizio: Could you explain where the numbers in your game are coming from? I couldn't quite understand the reasoning that far (see my question edit for details of what I thought about). $\endgroup$ – Mark S. Oct 31 '13 at 23:53

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.