# Solving for integers $m>8, n > 0$ for $2^m - 3^n = 13$

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}$$

• 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. Commented May 18, 2021 at 21:45
• @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. Commented May 18, 2021 at 21:45
• 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}$: Commented May 18, 2021 at 21:53
• @JohnOmielan Thanks for catching that. I had attempted a different approach originally which didn't work. I'll clean it up. Commented May 19, 2021 at 3:37
• $257$. I missed that in my review. Commented May 19, 2021 at 3:48

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$

Diophantine equation power of 7 and 2

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

• @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 Commented May 19, 2021 at 16:12
• 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.. :-) Commented May 19, 2021 at 16:44

$$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).$$

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{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}\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{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}\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.