# Given an odd $x$ there is an $m,n$ such that $2^n + 1 = 3^m x$?

I'm curious about this question: Is it true that for any odd number $x\in 2\mathbb N + 1$ there exists numbers $m,n\in \mathbb N \cup \{0\}$ such that $$2^n+1 = 3^mx$$

Edit: I'm not trying to make this over-complicated and maybe there is somethng easier than what I am thinking. But, if Pillai's conjecture is true then the answer should be negative for most $x$.

• I suppose $x=27$ has no solution Apr 13, 2015 at 10:13
• I've fixed the title to $2^n + 1 = 3^m x$. Apr 13, 2015 at 11:41

$7$ is one such number than cannot be expressed as $(2^n+1)/3^m$. For otherwise $3^m\cdot7=2^n+1$ for some $m,n$ positive integers. Thus $2^n+1=0 \mod 7$. But $2^n$ cannot have in $\mod 7$ values other than $2,4,1$ and so $2^n+1$ can have values only $2,3,5$ and none of these are $0\mod 7$.

• Please use mathstyle. Apr 13, 2015 at 12:03
• I took the liberty to review and edit it with $\TeX$-formatting. @Adelafif: Feel free to change if either if I made a mistake or it can be improved to match your intention. Apr 13, 2015 at 12:06
• BTW: There is no need to write $(2^n)+1$ rather than $2^n+1$ since order of operations make those equal, and the latter is the simplest form. Apr 13, 2015 at 12:08

Here are some$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}\newcommand\ifs{\text{if }}\let\v\nu$ criteria. Either way, I don't expect there to be a simple characterisation of such $x$.

• If $m>0$, then for $2^n+1$ to be a multiple of $3$, $n$ should be odd. From $2^n+1\equiv0\pmod x$ we have $(2^{(n+1)/2})^2\equiv-2\pmod x$, so $-2$ is a quadratic residue modulo $x$. Because $$\leg{-2}p=\leg{-1}p\leg2p=\begin{cases}-1&\ifs p\equiv5,7\pmod8\\1&\ifs p\equiv1,3\pmod8\end{cases}$$ we obtain that every prime divisor of $x$ is $\equiv1,3\pmod8$. (Because $3^2\equiv1\pmod8$ this implies in particular that $x\equiv1,3\pmod8$.)
If $m=0$ we simply have $x=2^n+1$ as a necessary and sufficient condition.
• By Zsigmondy's theorem, if $n$ has $\tau(n)$ positive divisors, then $2^n+1$ has at least $\tau(n)$ distinct prime divisors (unless $n=3$). This lets us conclude for example that $x$ cannot be a power of $3$ (though you might prove this using more elementary methods) unless for $x=1,3,9$. Also, if $x$ is given, Zsigmondy gives an upper bound on the number of prime divisors of $n$.
• If $m>0$ the Lifting The Exponent gives the exact exponent of $3$ in the factorisation of $n$:

Lemma. (Lifting The Exponent, special case) Let $p$ be an odd prime and $a,b\in\mathbb Z$ such that $p\mid a+b$ but $p\nmid a$. If $k$ is odd, then $\v_p(a^k+b^k)=\v_p(a+b)+\v_p(k)$, where $\v_p(k)$ denotes the exponent of $p$ in the prime factorisation of $k$.

So if $m>0$, then $n$ is odd hence $\v_p(n)=m-1$ by LTE. Combined with Zsigmondy this gives some more interesting partial results, such as: if $x=p^k$ is a prime power (with $p>3$ because $p=3$ is impossible, see above), then $n$ is prime. If $n>3$, then by LTE we have $m=1$, so $2^n+1=3p^k$.

• Thanks. Though I marked a post as the answer, I do appreciate a more general answer like the one you are trying to do. Apr 13, 2015 at 11:57
• Can someone help, does this mean that the question is true? Aug 6, 2022 at 9:57

For $x > 8$, $n \geq 3$, so $2^n + 1 = 1 \mod 8$.

$3^m = \begin{cases}3 \mod 8 & \text{ if } m \text{ odd} \\ 1 \mod 8 & \text{ if } m \text { even}\end{cases}$

Looking at the equation $\mod 8$, we must therefore have

$1 = 3x \mod 8$ or $1 = x \mod 8$

So any solution must have $x = 1 \mod 8$ or $x = 3 \mod 8$, since the inverse of $3 \mod 8$ is $3$. So there are no solutions with $x > 8$ and $x = 5 \mod 8$ or $x = 7 \mod 8$ .

• You mean any solution must be x=3 mod 8 (since it should be the inverse of 3 mod 8). Well ok, at least we have restricted the possible solutions mod 8... Apr 13, 2015 at 11:03