5
$\begingroup$

Let $m,n$ be integers such that:

$$2^m - 3^n = 13$$

$m > 8$ since $2^8 - 3^5 = 13$.

I am trying to either find a solution or prove that no solution exists.

I tried to use an argument similar to this one for $2^m - 3^n = 5$ where $m > 5$.

$3^n \equiv -13 \pmod {512}$ if and only if $n \equiv{69} \pmod {128}$

Is there a straight forward way to complete the argument? Is there a better way to answer the question for $2^m - 3^n = 13$ with $m > 8$?


Edit:

Adding context for question:

I have been trying to understand why it is so difficult to establish a lower bound to $2^m - 3^n$ when $2^m > 3^n$. This came out of thinking about the Collatz Conjecture.

It occurs to me that for $m \ge 3$, $2^m - 3^n$ is congruent to either $5$ or $7$ modulo $8$ (since $-3^{2i} \equiv 7 \pmod 8$ and $-3^{2i+1} \equiv 5 \pmod 8$)

For $2^m - 3^n \equiv 7 \pmod {12}$, $m$ and $n$ are even, so the lower bound is at least $3^{n/2}$ since:

$$2^m - 3^n = (2^{m/2} - 3^{n/2})(2^{m/2} + 3^{m/2}) > 0$$

and

$$2^{m/2} - 3^{m/2} \ge 1$$

So, to reach a lower bound, I need to better understand the implications of $2^m - 3^n \equiv 5 \pmod 8$ and $2^m - 3^n \equiv 7 \pmod 8$ when $2^m - 3^n \not\equiv 7 \pmod {12}$.

I am also working to better understand this blog post by Terence Tao.


Edit 2:

I think that I can complete the argument using the congruence classes of $257$.

Here's my thinking:

Since $n \equiv 69 \pmod {128}$, $3^n \equiv 224$ or $33 \pmod {257}$

Then $2^m \equiv 3^n + 13 \pmod {257}$ which means $2^m \equiv 237$ or $46 \pmod {257}$

But there is no such solution of $2^m$ since for each $2^m$, there exists an integer $i$ such that $2^m \equiv \pm 2^{i} \pmod {257}$ and there is no such $i$ where $\pm 2^{i} \equiv {237} \pmod {257}$ or $\pm 2^{i} \equiv {46} \pmod {257}$

$\endgroup$
8
  • 1
    $\begingroup$ A $\pmod{13}$ argument establishes that $4 ~| ~m$ and that $(m/4) \equiv n \pmod{3}.$ Unfortunately, I see no way of using this to attack the problem. $\endgroup$ Commented May 18, 2021 at 21:45
  • 2
    $\begingroup$ @LarryFreeman FYI, in case you haven't checked it out yet, the Generalization section of Wikipedia's "Catalan's conjecture" article states that, up to $10^{18}$, there are only $3$ perfect powers (i.e., integers each to a power $\gt 1$) whose difference is equal to $13$. They are $7^2 - 6^2$, your $2^8 - 3^5$, and $17^3 - 70^2$. This suggests there are likely no other solutions for any perfect powers, including your specific case. However, I haven't yet determined any rigorous way to prove this for your question. $\endgroup$ Commented May 18, 2021 at 21:45
  • 2
    $\begingroup$ In addition to @JohnOmielan 's link to WP, OEIS links to this list of all known solutions up to a difference of $100$, for every perfect power up to $10^{18}$: $\endgroup$ Commented May 18, 2021 at 21:53
  • 1
    $\begingroup$ @JohnOmielan Thanks for catching that. I had attempted a different approach originally which didn't work. I'll clean it up. $\endgroup$ Commented May 19, 2021 at 3:37
  • 1
    $\begingroup$ $257$. I missed that in my review. $\endgroup$ Commented May 19, 2021 at 3:48

3 Answers 3

6
$\begingroup$

we have $$ 256(2^x - 1) = 243(3^y - 1) $$ and we assume $x,y \geq 1$

since $2^x \equiv 1 \pmod {243}$ we calculate that $162 | x.$

Next, $2^{162} - 1$ is divisible by the prime $262657.$

since $3^y \equiv 1 \pmod {262657}$ we calculate that $14592 | y.$ In particular, $256|y.$

Well, $3^{256} - 1$ is divisible by 1024. So that $ 256(2^x - 1) $ is divisible by 1024, which is a contradiction of $x \geq 1$

similar:

https://math.stackexchange.com/users/292972/gyumin-roh

Exponential Diophantine equation $7^y + 2 = 3^x$ Gyumin Roh answer from 2015

Elementary solution of exponential Diophantine equation $2^x - 3^y = 7$.

Elementary solution of exponential Diophantine equation $2^x - 3^y = 7$. ME! 41, 31, 241, 17

Finding solutions to the diophantine equation $7^a=3^b+100$ 343 - 243 = 100

http://math.stackexchange.com/questions/2100780/is-2m-1-ever-a-power-of-3-for-m-3/2100847#2100847

The diophantine equation $5\times 2^{x-4}=3^y-1$

Equation in integers $7^x-3^y=4$

Solve in $\mathbb N^{2}$ the following equation : $5^{2x}-3\cdot2^{2y}+5^{x}2^{y-1}-2^{y-1}-2\cdot5^{x}+1=0$

Solve Diophantine equation: $2^x=5^y+3$ for non-negative integers $x,y$. 128 - 125 = 3

Diophantine equation power of 7 and 2

Find natural numbers a,b such that $|3^a-2^b|=1$ did +-1

Finding all natural $x$, $y$, $z$ satisfying $7^x+1=3^y+5^z$

$\endgroup$
2
  • 2
    $\begingroup$ @LarryFreeman I wrote two programs years ago. The first one is called "order." Telling it prime $p$ and target $t,$ it runs a loop and reports the first $n$ such that $p^n \equiv 1 \pmod t.$ The other one just does its best to factor $p^n - 1.$ In this case, most priime factors of $2^{162} - 1$ did not offer any useful restriction on $y,$ then suddenly the 262657 gave the whole story. Let me paste in links to previous such problems, you might enjoy working through some with small numbers $\endgroup$
    – Will Jagy
    Commented May 19, 2021 at 16:12
  • 1
    $\begingroup$ Awesome. Thanks very much for the explanation! I deleted my previous comment because I suspected that I would be able to figure it out based on John Omielan's details in his answer.. :-) $\endgroup$ Commented May 19, 2021 at 16:44
2
$\begingroup$

$$2^{m} - 3^{n} = 13\tag{1}$$

An argument mod $3$ shows that $m$ is even, then let $m=2a.$
We can take the three cases $n=3b, n=3b+1,$ and $n=3b+2.$
The problem can be reduced to finding the integer points on elliptic curves as follows.

$\bullet n=3b$
Let $X=3^{b}, Y=2^{a}$, then we get $Y^2 =X^3 + 13.$
According to LMFDB, this elliptic curve has no integral solution.

$\bullet n=3b+1$
Let $X=3\cdot3^{b}, Y=3\cdot2^{a}$, then we get $Y^2 =X^3 + 117.$
This elliptic curve has integral solution $(X,Y)=(3,\pm 12).$
From this solution, we get $(m,n)=(4,1).$

$\bullet n=3b+2$
Let $X=9\cdot3^{b}, Y=9\cdot2^{a}$, then we get $Y^2 =X^3 + 1053.$
This elliptic curve has integral solutions $(X,Y)=(-9,\pm 18)$, $(27,\pm 144).$
From $(27,\pm 144)$ we get $(m,n)=(8,5).$

Hence there are only two integral solutions $(m,n)=(4,1),(8,5).$

$\endgroup$
0
2
$\begingroup$

You don't state how you determined your various results modulo $512$ and $257$, i.e., all by hand or with the help, at least to some extent, of a computer program (other than a calculator). In either case, here is a way to help manually verify what you wrote.

From Euler's theorem and Lagrange's theorem, the multiplicative order, i.e., $\operatorname{ord}_{512}(3)$, must divide the Euler's totient function value, which is $\varphi(512) = 256 = 2^{8}$. Thus, we only need to check the modulo $512$ values of $3$ to exponents of powers of $2$, up to $128$. This can be done using repeated squaring and simplifying modulo $512$, resulting in

$$\begin{equation}\begin{aligned} 3^1 & \equiv 3 \pmod{512} \\ 3^2 & \equiv 9 \pmod{512} \\ 3^4 & \equiv 81 \pmod{512} \\ 3^8 & \equiv 81^2 \equiv 6\text{,}561 \equiv 417 \pmod{512} \\ 3^{16} & \equiv 417^2 \equiv 173\text{,}889 \equiv 321 \pmod{512} \\ 3^{32} & \equiv 321^2 \equiv 103\text{,}041 \equiv 129 \pmod{512} \\ 3^{64} & \equiv 129^2 \equiv 16\text{,}641 \equiv 257 \pmod{512} \\ 3^{128} & \equiv 257^2 \equiv 66\text{,}049 \equiv 1 \pmod{512} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Thus, this gives that $\operatorname{ord}_{512}(3) = 128$, which means the solutions of $n$ in

$$3^n \equiv -13 \pmod{512} \tag{2}\label{eq2A}$$

must be congruent to each other modulo $128$. To show the smallest positive integer $n$ is $69 = 64 + 4 + 1$, we get using this binary expansion and \eqref{eq1A} that

$$3^{69} \equiv (257)(81)(3) \equiv 62\text{,}451 \equiv 499 \equiv -13 \pmod{512} \tag{3}\label{eq3A}$$

This confirms your statement that $n \equiv 69 \pmod{128}$.

To check further, due to $128$ dividing into it's Euler totient value, it's helpful to, as you did, use the next larger Fermat prime, with this being $257$. Similar to what was done in \eqref{eq1A}, with modulo $257$ we get

$$\begin{equation}\begin{aligned} 3^8 & \equiv 81^2 \equiv 6\text{,}561 \equiv 136 \pmod{257} \\ 3^{16} & \equiv 136^2 \equiv 18\text{,}496 \equiv 249 \equiv -8 \pmod{257} \\ 3^{32} & \equiv (-8)^2 \equiv 64 \pmod{257} \\ 3^{64} & \equiv 64^2 \equiv 4\text{,}096 \equiv 241 \equiv -16 \pmod{257} \\ 3^{128} & \equiv (-16)^2 \equiv 256 \equiv -1 \pmod{257} \\ 3^{256} & \equiv (-1)^2 \equiv 1 \pmod{257} \\ \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

This shows that $\operatorname{ord}_{257}(3) = 256$. Also, since $3^{128} \equiv -1 \pmod{257}$, this means for $n \equiv 69 \pmod{128}$, we get $3^{n} \equiv \pm 3^{69} \pmod{257}$. Using the binary expansion of $69$, similar to before, gives

$$3^{69} \equiv (3)(81)(-16) \equiv -33 \equiv 224 \pmod{257} \tag{5}\label{eq5A}$$

Therefore, your result there is correct, which means your next conclusion is also correct, i.e., that

$$2^m \equiv 237 \text{ or } 46 \pmod{257} \tag{6}\label{eq6A}$$

In your last paragraph, you're using a manual short-cut in that, since $2^{8} \equiv 256 \equiv -1$, we only need to check just the $\pm$ values for $2 \le m \le 7$. This can, of course, easily be done manually to verify that since none of $46$ and $237$, as well as their negative congruences of $257 - 46 = 211$ and $257 - 237 = 20$, are a power of $2$, there is no $m$ which satisfies \eqref{eq6A}. Thus, this confirms your proof is correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .