# Does 2^m = 3^n + r have finitely many solutions for every r?

Is it true that for every integer $r$, the equation $2^m = 3^n + r$ has at most a finite number of integer solutions? I understand that this is a special case of Pillai's conjecture, which is unsolved.

If the statement is true, then can we verify the finiteness of the solution set using modular arithmetic? To be precise, is the following proposition true?

$$\forall r,\ \exists M,\ \exists N,\ \forall m,n \ge N,\ \ 2^m \not\equiv 3^n + r \pmod{M}$$

I have verified the proposition for $0 \le r \le 12$, and found the least possible modulus $M(r)$ for each $r$ in this interval. Note that $M(r) = 2$ if $r$ is even.

$M(1) = 8$, $M(3) = 3$, $M(5) = 1088$, $M(7) = 1632$, $M(9) = 3$, $M(11) = 8$.

-
I have extended the calculation to $0 \le r \le 100$. M(r) = 3 for r = 3 (mod 6); M(r) = 8 for r = 17, 19, 25, 35, 41, 43, 49, 59, 65, 67, 73, 83, 89, 91, 97; M(r) = 60 for r = 31, 53, 79, 85, 95; M(13) = 131584; M(23) = 1088; M(29) = 117; M(37) = 21951; M(47) = 65972; M(55) = 999; M(61) = 252; M(71) = 63; M(77) = 28. – Dave R Mar 21 '10 at 5:46

Yes, it is true that this kind of equation ax+by=c, where a,b,c are non-zero and fixed and x,y are allowed to only have prime factors in a finite set, has only finitely many solutions. This is a special case of Siegel's theorem on integral points on curves.

Your second question may be unknown in the generality you pose. It is interesting that it holds. A remark: if there is a solution to $2^m = 3^n + r$, then $2^{m+k\phi(M)} \equiv 3^{n+k\phi(M)} + r (\mod M)$ for all $k,M$ if $(M,6)=1$, so if $M$ exists in this case, then $(M,6)>1$. If there is no solution to the equation $2^m = 3^n + r$, then the existence of $M$ (with $N=0$) is a special case of a conjecture of Skolem.

T. Skolem: Anwendung exponentieller Kongruenzen zum Beweis der Unlösbarkeit gewisser diophantischer Gleichungen., Avh. Norske Vid. Akad. Oslo, 12 (1937), 1–16.

Another comment. There are no solutions when $r=11$ but $M=8$ doesn't work since $2^2 \equiv 3^2 + 11 \mod 8$. $M(11)=205$. (Edit: $M(11)=8$ is OK. I misunderstood the definition, see comments)

-
Thanks you for your very helpful comments. I am intrigued by the result concerning ax+by=c . I should really learn about elliptic curves! But $M = 8$ does work when $r = 11$, since we may assume that $m \ge 3$. – Dave R Mar 20 '10 at 3:34
What you say about M=8,r=11 doesn't make sense. You can also take m=6, if you don't like m=2. – Felipe Voloch Mar 20 '10 at 3:50
2^6 = 0 (mod 8). 3^n + 11 is never divisible by 8. – Dave R Mar 20 '10 at 3:53
Felipe, there seems to be some confusion over the definition of $M(r)$. You only need $2^m\not\equiv3^n+11 (\mod 8)$ for sufficiently large $m$ and $n$ to conclude that $M(11)\leq8$. – Jonas Meyer Mar 20 '10 at 7:30
OK, I understand now, M=8 shows that the set of solutions is finite and M=205 that is empty. What I said about m=6 doesn't make sense. – Felipe Voloch Mar 20 '10 at 12:18

I have no comment on your methods, and I know very little about this, but that case of Pillai's conjecture appears to have been solved in the 80's by Stroeker and Tijdeman [Edit: see below]. Here's a paper by Bennett from 2001 that shows more: http://www.math.ubc.ca/~bennett/B-CJM-Pillai.pdf. In particular, the number of solutions is at most 2 for each fixed $r$. More generally, Bennett shows that for fixed integers $a\geq2$, $b\geq2$, and $r\neq0$, there are at most 2 solutions $(m,n)$ to the equation $a^m=b^n+r$. The more general form of Pillai's conjecture allows $a$ and $b$ to vary and appears to still be unsolved.

Edit: What Stroeker and Tijdeman actually did was sharpen the result by showing that except when $r$ is in $\{-1,5,13\}$, your equation has at most one solution, and that in the exceptional cases it has two. The finiteness of the set of solutions $(m,n)$ to the equation $a^m=b^n+r$ had long been known, and Pallai himself gave some quantitative results on this using Siegel's Theorem. For finiteness alone without quantification, Bennett cites this 1918 Polya paper. My source for all of this is Bennett's paper.

-
What I said about Stroeker and Tijdeman is misleading (I will edit to clarify) and Felipe Voloch is right on with Siegel's theorem. Felipe also addressed the second question, and I'm not sure why this answer was accepted. – Jonas Meyer Mar 20 '10 at 6:27
I selected your answer because I was intrigued by Bennett's result, and because I could not accept both answers. I am grateful for both of your contributions. – Dave R Mar 20 '10 at 7:17
Thanks for explaining. I guess it seemed strange because I was merely interested and did some internet searching, whereas Felipe wrote based on his expertise. Also, I have nothing useful to say about your second question. – Jonas Meyer Mar 20 '10 at 8:07
I don't want this to be a point of contention, so I have accepted Felipe's answer instead. Thanks again for your help. – Dave R Mar 20 '10 at 9:18