# $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
I have a different opinion about the existence of such $t$ - I think it does not exist. But I would also very welcome to see a counterexample if it exists. –  Max Alekseyev Jun 29 '10 at 19:45
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

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.

-