# $3^n - 2^m = \pm 41$ is not possible. How to prove it?

$3^n - 2^m = \pm 41$ is not possible for integers $n$ and $m$. How to prove it?

• How many congruences have you tried? How about mod 9? – Charles Matthews Jun 29 '10 at 14:58
• The equation $3^n-2^m=\pm1$ in integers was fully solved by Levi ben Gerson ($\approx1320$). What's the trouble to do this one yourself by considering modulo 4 and 3 (or 9)? It looks a homework problem if you don't state your reasons and don't indicate your approaches. – Wadim Zudilin Jun 29 '10 at 14:59
• Wadim: if n is positive even, and m is congruent to 2 mod 6 (but not equal to 2), then 3^n - 2^m is congruent to +41 mod 8 and mod 9. So I don't see how "modulo 8 and modulo 9 suffice". – Michael Lugo Jun 29 '10 at 15:36
• If m and n are even ... well, any mathematician would know what to do next. – Charles Matthews Jun 29 '10 at 15:42
• If n and m are both even, then 41 is a difference of two squares, which factorises. – Fedor Petrov Jun 29 '10 at 15:44

The congruence $3^n - 2^m \equiv 41\pmod{60}$ has no solutions.

The congruence $3^n - 2^m \equiv -41\pmod{72}$ has no solutions.

• Very nice! Is there an integer $t$ such that $3^n-2^m=t$ has no solutions in non-negative integers $m,n$ but for which this cannot be proved by reducing the equation modulo $N$ as above for any $N$? I suspect so (number theory is too hard for this sort of technique to be that powerful) but it would be nice to know an explicit example! – Kevin Buzzard Jun 29 '10 at 19:37
• Kevin's question intrigued me. So I wondered if these moduli were special somehow. It turns out that $3^n-2^m\equiv 41$ fails modulo 601 (and then again at 6553) and $3^n-2^m\equiv -41$ fails modulo 1321. All of these moduli are primes (as that is what I restricted my search to). It seems that if we find a prime for which both 2 and 3 have relatively small orders, the chance that we hit $t$ gets small. – Pace Nielsen Jun 29 '10 at 21:16
• @Michael, you've done it modulo 72 yesterday! See your comment to mine above. Because $72=8\cdot 9$ (I believe). Modulo 60 is much less trivial, Max's answer is really nice. (In dreams I started to think of applying linear forms in logs. :-) ) – Wadim Zudilin Jun 30 '10 at 0:35
• @Kevin: I suggest that you turn your interrogative comment into a new question. It will get a lot more attention that way, and rightfully so, I think. – Pete L. Clark Jun 30 '10 at 7:48
• @Pete: done: mathoverflow.net/questions/30031/… – Kevin Buzzard Jun 30 '10 at 10:39

As a valuable hint for solving the problem, I consider the following extract from my lectures on elementary number theory.

Theorem ($\approx1320$; Levi ben Gerson 1288--1344). The equations $$(1) \quad 3^p-2^q=1$$ and $$(2) \quad 2^p-3^q=1$$ have no solutions in integers $p,q>1$, except the solution $p=2$, $q=3$ to equation (1).

Proof. (1) If $p=2k+1$, then $$2^q=3^p-1=3\cdot9^k-1\equiv2\pmod4,$$ which is impossible for $q>1$.

If $p=2k$, then $2^q=3^p-1=(3^k-1)(3^k+1)$ implying $3^k-1=2^u$ and $3^k+1=2^v$. Since $2^v-2^u=(3^k+1)-(3^k-1)=2$, we have $v=2$ and $u=1$. This corresponds to the unique solution $q=u+v=3$ and $p=2$.

(2) If $q\ge1$, then $3^q+1$ is not divisible by~$8$. Indeed, if $q=2k$, then $3^q+1=9^k+1\equiv2\pmod8$; and if $q=2k+1$, then $3^q+1=3\cdot9^k+1\equiv4\pmod8$. Therefore $p\le2$, hence $p=2$. The latter implies $q=1$ which does not correspond to a solution.