Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks! $:)$

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

3 Answers 3

up vote 1 down vote accepted

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

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

share|improve this answer

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

]

share|improve this answer

Your Answer

 
discard

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.