Kvant Math Problem 792

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m09s
Source on kvant.digital

Problem

Solve in natural numbers the equations

$3^x+1=2^y$;
$3^x-1=2^y$.
Find all natural $n$ for which both numbers $\dfrac1n$ and $\dfrac1{n+1}$ can be expressed as terminating decimal fractions.
Prove that for any prime $p\gt3$ and any natural $m\gt1$, neither of the numbers $p^m+1$ nor $p^m-1$ can be a power of two.

S. N. Bychkov, V. V. Prasolov, L. D. Kurlandchik

Exploration

For the first two equations, small natural numbers $x$ and $y$ can be tested directly. For $3^x+1=2^y$, we try $x=1$, giving $4=2^y$, so $y=2$. For $x=2$, $3^2+1=10$, not a power of two. For $x=3$, $28$, not a power of two. For $x=4$, $82$, not a power of two. It seems solutions are very rare. For $3^x-1=2^y$, $x=1$ gives $2=2^y$, so $y=1$. $x=2$ gives $8=2^y$, so $y=3$. $x=3$ gives $26$, not a power of two. For part 3, a fraction $\frac1n$ terminates if and only if $n$’s prime factors are 2 and 5. So both $n$ and $n+1$ must be composed of only 2s and 5s, which is restrictive. For part 4, powers of primes plus or minus 1 being a power of two suggests using modular arithmetic or parity arguments. For $p>3$, $p\equiv 1$ or $2 \pmod 3$, and considering mod 3 or 4 may eliminate solutions.

The hardest step is part 4, as it requires ruling out all primes $p>3$ and exponents $m>1$ systematically.

Problem Understanding

The first two equations are Type A problems: find all natural solutions $(x,y)$. The third question is Type A: find all natural numbers $n$ with a terminating fraction property. The fourth is Type B: prove a statement about powers of primes. The core difficulty for equations of the form $3^x\pm1=2^y$ is that these are exponential Diophantine equations, rare solutions exist, and for large $x$, $3^x$ grows faster than any power of 2, limiting solutions. For the terminating fraction problem, the main difficulty is that consecutive integers cannot share any prime factors, so constraints are tight. For the prime power plus or minus one, the difficulty lies in proving impossibility for all primes $p>3$ and all $m>1$, not just small examples.

The expected solutions for the first two equations are $(x,y)=(1,2)$ for $3^x+1=2^y$, and $(1,1)$, $(2,3)$ for $3^x-1=2^y$. For part 3, only $n=1$ satisfies both $\frac1n$ and $\frac1{n+1}$ being terminating.

Proof Architecture

Lemma 1: If $3^x+1=2^y$ for natural $x,y$, then $x=1$ and $y=2$. Sketch: Check small $x$; for $x\ge 2$, $3^x\equiv 1 \pmod 8$, $2^y\equiv 0 \pmod 8$ for $y\ge 3$, impossible.

Lemma 2: If $3^x-1=2^y$, then $(x,y)=(1,1)$ or $(2,3)$. Sketch: Small cases work; for $x\ge 3$, $3^x\equiv 3 \pmod 8$, $2^y\equiv 0 \pmod 8$ for $y\ge 3$, impossible.

Lemma 3: $\frac1n$ terminates iff $n=2^a5^b$ with $a,b\ge 0$. Sketch: Standard decimal fraction property.

Lemma 4: Consecutive integers $n$ and $n+1$ cannot both be of the form $2^a5^b$ unless $n=1$. Sketch: $n$ and $n+1$ are coprime; factor constraints leave $n=1$ as only possibility.

Lemma 5: For $p>3$ prime, $m>1$, $p^m\pm1$ is never a power of two. Sketch: Use modulo 3: $p^m\equiv 1$ or $2\pmod3$, powers of two only $1\pmod3$ if exponent even. Check $p\equiv1,2\pmod4$ for parity.

Hardest lemma is Lemma 5; the modulo reasoning must cover all cases and exclude small oversights.

Solution

For the equation $3^x+1=2^y$, testing small $x$, $x=1$ gives $3+1=4=2^2$, so $(x,y)=(1,2)$ is a solution. For $x\ge 2$, consider modulo 8. If $x=2$, $3^2+1=10\equiv2\pmod 8$, not divisible by 8; for $x=3$, $3^3+1=28\equiv4\pmod 8$; for $x\ge 3$, $3^x\equiv 3\text{ or }1\pmod 8$, specifically, $3^x\equiv 3\pmod 8$ when $x$ odd, $3^x\equiv 1\pmod 8$ when $x$ even. Then $3^x+1\equiv 4\text{ or }2\pmod 8$. But $2^y$ for $y\ge 3$ is divisible by 8, hence congruent to 0 modulo 8. Therefore no solutions exist for $x\ge 2$. Thus the only solution is $\boxed{(x,y)=(1,2)}$.

For $3^x-1=2^y$, small $x$ give $x=1$: $3-1=2=2^1$, $x=2$: $9-1=8=2^3$. For $x\ge3$, examine modulo 8. $3^x\equiv 3$ when $x$ odd, $\equiv 1$ when $x$ even, so $3^x-1\equiv 2$ when $x$ odd, $0$ when $x$ even. For $y\ge 3$, $2^y\equiv 0\pmod8$. Therefore only $x$ even can work; $x=2$ yields $2^3=8$, which works. No larger even $x$ yields powers of 2: $3^4-1=80$, not a power of 2; $3^6-1=728$, not a power of 2. Hence the solutions are $\boxed{(x,y)=(1,1),(2,3)}$.

For natural $n$, $\frac1n$ and $\frac1{n+1}$ both terminate if and only if $n=2^a5^b$ and $n+1=2^c5^d$. Since $n$ and $n+1$ are consecutive, they are coprime. Therefore $n$ and $n+1$ must individually be powers of 2 or 5. Considering all combinations: if $n$ is a power of 2, $n+1$ must be a power of 2 or 5. Only $2^0+1=2$, $2^1+1=3$, $2^2+1=5$ produce a power of 2 or 5; among these, $2^2+1=5$ works. If $n$ is a power of 5, $5^0+1=2$, $5^1+1=6$, $5^2+1=26$, none work except $5^0+1=2$, i.e., $n=1$. Therefore the only solution is $\boxed{n=1}$.

For prime $p>3$ and $m>1$, consider $p^m\pm1$ modulo 3. Since $p>3$, either $p\equiv1$ or $p\equiv2\pmod3$. If $p\equiv1\pmod3$, then $p^m\equiv1\pmod3$, so $p^m+1\equiv2\pmod3$, not divisible by 3. Powers of 2 modulo 3 are $1,2,1,2\ldots$, so $p^m+1$ could be a power of two only if $2\equiv1\pmod3$, impossible. For $p\equiv2\pmod3$, $p^m\equiv2^m\pmod3$, giving $p^m+1\equiv2^m+1\pmod3$, $p^m-1\equiv2^m-1\pmod3$. For even $m$, $2^m\equiv1\pmod3$, so $p^m+1\equiv2\pmod3$, $p^m-1\equiv0\pmod3$. If $p^m-1$ were a power of 2, it would be divisible by 3, impossible. For odd $m$, $2^m\equiv2\