11
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ How many congruences have you tried? How about mod 9? $\endgroup$ Jun 29, 2010 at 14:58
  • 6
    $\begingroup$ 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. $\endgroup$ Jun 29, 2010 at 14:59
  • 2
    $\begingroup$ 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". $\endgroup$ Jun 29, 2010 at 15:36
  • 2
    $\begingroup$ If m and n are even ... well, any mathematician would know what to do next. $\endgroup$ Jun 29, 2010 at 15:42
  • 2
    $\begingroup$ If n and m are both even, then 41 is a difference of two squares, which factorises. $\endgroup$ Jun 29, 2010 at 15:44

2 Answers 2

23
$\begingroup$

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.

$\endgroup$
7
  • 6
    $\begingroup$ 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! $\endgroup$ Jun 29, 2010 at 19:37
  • 6
    $\begingroup$ 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. $\endgroup$ Jun 29, 2010 at 21:16
  • 5
    $\begingroup$ @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. :-) ) $\endgroup$ Jun 30, 2010 at 0:35
  • 4
    $\begingroup$ @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. $\endgroup$ Jun 30, 2010 at 7:48
  • 1
    $\begingroup$ @Pete: done: mathoverflow.net/questions/30031/… $\endgroup$ Jun 30, 2010 at 10:39
15
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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