# Solutions for $2^i = 3^ j - 1$ or $2^i = 3^ j + 1$

Are there any solutions for $2^i = 3^ j - 1$ or $2^i = 3^ j + 1$, for $i>3$ and $j>2$ ?

Thanks! $:)$

-
look up the Catalan conjecture, now a theorem. –  Will Jagy Dec 24 '12 at 0:32
Wikipedia –  MJD Dec 24 '12 at 0:59
...also, that question was here a couple of times. Just try to find them here in MSE –  Gottfried Helms Dec 24 '12 at 1:00
That special (simple) case of the catalan-conjecture was already made by the medieval Gersonides in the 13'th –  Gottfried Helms Dec 24 '12 at 2:03

Here is a very short solution for the second one: By little Fermat and Euler's totient theorem we know that with some nonnegative integers k and j $$2^{2 \cdot 3^j k} - 1 \equiv 0 \pmod{ 3^{j+1}}$$ Thus $$(2^{3^j k})^2 - 1 \equiv 0 \pmod{ 3^{j+1}} \\ (2^{3^j k} - 1)(2^{3^j k} + 1) \equiv 0 \pmod{ 3^{j+1}}$$ But here the factors on the lhs differ by 2 and thus cannot both be divisible by 3, and so must have other factors besides powers of 3, except for the case where one parenthese equals 1. So we can determine the single solution : $j=0,k=1 \to (1)(3) =3^1=2^2-1$ [edit: corrected $\to k=1$]

-
This solution is incorrect, because it is false in general that $a^x \equiv 1 \pmod{n} \implies \phi(n)|x$. –  dinoboy Dec 24 '12 at 5:58
@dino: where is the error with the concrete values 2 and 3 in this case? –  Gottfried Helms Dec 24 '12 at 9:04
Well it happens to hold for that case, but the proof is slightly nontrivial and clearly not a direct application of Euler's Theorem. –  dinoboy Dec 24 '12 at 21:13

Gottfried Helms has dealt with $2^i=3^j+1$. For completeness we deal with $2^i =3^j-1$.

This has the solutions $i=j=1$ and $i=3$, $j=2$. We show there are no others.

First we deal with odd $j$. Note that $$3^j-1=(3-1)\left(3^{j-1}+3^{j-2}+\cdots +1\right).$$ The term $3^{j-1}+3^{j-2}+\cdots +1$ is the sum of an odd number of odd numbers, so it is odd. It follows that if $j$ is odd, then $3^j-1$ can only be a power of $2$ if $j=1$.

Next we deal with even $j$, say $j=2k$. Then $3^j=3^{2k}-1=(3^k-1)(3^k+1)$. This can be a power of $2$ only if both $3^k-1$ and $3^k+1$ are powers of $2$. But the only two powers of $2$ that differ by $2$ are $2$ and $4$. It follows that $j=2$ and $i=3$.

-

Observe that $2$ is a primitive root of $3^k$ where $k$ is natural number(Proof below).

(1)So if $2^i=3^{j+1}+1,2^i\equiv1\pmod {3^{j+1}}$ $\implies \phi(3^{j+1})\mid i \implies 2\cdot 3^j\mid i$

So, the minimum possible integral value of $i$ is $2\cdot 3^j$

If $j=0,i_{min}=2,2^i-3^{j+1}=2^2-3^1=1$

If $j=1,i_{min}=2\cdot3^1=6,2^i-3^{j+1}=2^6-3^2>1$

If $j=2,i_{min}=2\cdot3^2=18,2^i-3^{j+1}=2^{18}-3^3>1$

Clearly, the difference diverges from $1$ with the increment of $j$ and $i$.

It can also proved as follows: $2^i-3^{j+1}-1=2^{2\cdot 3^j}-3^{j+1}-1=4^{3^j}-3^{j+1}$ $=(3+1)^{3^j}-3^{j+1}-1=\sum_{1\le k\le 3^j-1}\binom{3^j}k3^j>0$ if $j>0$

(2) So if $2^i=3^{j+1}-1,2^i\equiv-1\pmod {3^{j+1}}$ $\implies \frac{\phi(3^{j+1})}2\mid i$ but $\phi(3^{j+1})\not\mid i$

So, the minimum possible integral value of $i$ is $3^j$

If $j=0,i_{min}=1,2^i-3^{j+1}=2^1-3^1=-1$

If $j=1,i_{min}=3,2^i-3^{j+1}=2^3-3^2=-1$

If $j=2,i_{min}=3^2=9,2^i-3^{j+1}=2^9-3^{2+1}>-1$

Clearly, the difference diverges from $-1$ with the increment of $j$ and $i$.

[

Proof:

$2\equiv -1\pmod 3, 2^2\equiv1\implies ord_32=2$

$2^2=4,2^3=8\equiv-1\pmod {3^2},2^6\equiv1\implies ord_{(3^2)}2=6=2\cdot 3=\phi(9)$

From this, $ord_{(3^3)}2=2\cdot 3^2=\phi(27)$

As $ord_{(3^2)}2=6=2\cdot 3,ord_{(3^3)}2=2\cdot 3^2\implies ord_{(3^4)}2=2\cdot3^3=\phi(81)$

Proceeding this way, we can prove $ord_{(3^n)}2=2\cdot3^{n-1}=\phi(3^n)$

]

-