Helping A Power Of 2 Reach A Power Of 3

By Lifting The Exponent, we have $\begin{aligned} 3^x - 1^x &= 2^xy\\ \nu_2(3^x - 1) &\geq x\\ \nu_2(3-1)+\nu_2(x)+\nu_2(3+1)-1 &\geq x\\ \nu_2(x) &\geq x-2\\ x &\geq 2^{x-2} \end{aligned}$ Note that $\forall x \geq 5, x<2^{x-2}$ . Thus, we merely check $x=1,2,3,4$ , finding only $x=1, 2, 4$ satisfy, yielding $y=1,2,5$ . Therefore, there are 3 pairs satisfying.

We are looking for $x$ such that $2^x | (3^x-1)$ . Here is a lemma:

Lemma: Let $x = 2^a b$ , where $b$ is odd. If $x$ is odd (so $a = 0$ ), the highest power of $2$ dividing $3^x-1$ is $2^1$ . If $x$ is even ( $a \ge 1$ ), the highest power of $2$ dividing $3^x-1$ is $2^{a+2}$ .

Proof: This is easy when $a = 0$ , since $3^x-1 \equiv 2$ mod $4$ . Now write $3^x-1 = (3^{x/2}-1)(3^{x/2}+1)$ When $a = 1$ , the first factor is $2$ mod $4$ and the second factor is $4$ mod $8$ . So the highest power of $2$ dividing $3^x-1$ is $2^3$ . When $a$ is larger, we can use induction; the highest power of $2$ dividing the first factor is $2^{a+1}$ , and the second factor is $2$ mod $4$ , because $x/2$ is even. So the highest power of $2$ dividing the product is $2^{a+1} \cdot 2^1 = 2^{a+2}$ . This proves the lemma. $\square$

So we are looking for $x$ such that $x \le 1$ if $x$ is odd, and $x=2^a b \le a+2$ when $a$ is even. Clearly $x = 1$ is the only odd solution, and otherwise we have $2^a \le 2^a b \le a+2$ . The graphs of $y=2^x$ and $y = x+2$ intersect at $(2,4)$ , and the slope of $y = 2^x$ is greater than the slope of $y=x+2$ (which is $1$ ) for $x \ge 1$ (calculus exercise!), so for $a > 2$ , $2^a > a+2$ . So we can exclude $a > 2$ . For $a = 1$ we get $2b \le 3$ so $b = 1$ , and for $a =2$ we get $4b \le 4$ so $b = 1$ . So the only solutions are $x=1,2,4$ . The answer is $\fbox{3}$ .

Rewrite the equation as

$\large\ { 3 }^{ x } - 1 = { 2 }^{ x }y$ .

We can now infer that $x$ cannot exceed the exponent of $2$ in the prime factorization of ${ 3 }^{ x } - 1$ . Let us estimate how large the exponent is. Note that modulo $4$ the number ${ 3 }^{ n } - 1$ is congruent to $2$ if $n$ is odd and to $0$ if $n$ is even. This observation shows that it is worth factoring $x$ as ${ 2 }^{ m }(2n + 1)$ , with $m$ and $n$ non-negative integers. We can then write

$\large\ { 3 }^{ { x } } - 1 = { 3 }^{ { 2 }^{ m }(2n+1) } - 1 = { ({ 3 }^{ 2n+1 })^{ { 2 }^{ m } } - 1 = ({ 3 }^{ 2n+1 } - 1)({ 3 }^{ 2n+1 } - 1)\prod _{ k = 1 }^{ m - 1 }{ \left( \left( { 3 }^{ 2n + 1 } \right) ^{ 2k } + 1 \right) } }$ .

Taken modulo $8$ , the first two factors are $2$ , respectively $4$ . Hence they contribute a factor of ${ 2 }^{ 3 }$ to the product ${ 3 }^{ x } - 1$ . Each of the factor contributes a factor of $2$ . Consequently, the exponent of $2$ in ${ 3 }^{ x } - 1$ is $m + 2$ . We obtain the inequality $x \le m + 2$ , which translates to

${ 2 }^{ m }({ 2 }^{ n } + 1) \le (m + 2)$ .

In particular, ${ 2 }^{ m } \le m + 2$ , which restricts us to $m = 0, 1, 2$ . An easy check yields the solutions to the original equation $(x, y) = (1, 1) ; (2, 2) ; (4, 5)$ . In total, there are $\boxed{3}$ positive pairs.