MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.