Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Solve for integer $m$ and $n:$ $$2^m = 3^n + 5$$
My Attempt: Easy to guess two solutions namely $(3,1)$ and $(5,3)$. Also easy to see that a solution will exist iff $m > 0$ and $n > 0$.
Rewriting it as $2^m - 2 = 3^n + 3$ we get $2^m = 2 \mod 3 \Rightarrow m = 1 \mod 2$ and $3^n = 1 \mod 2 \Rightarrow n = 1 \mod 2$, hence $m$ and $n$ are both odd. Beyond this, I could not figure out what approach to use.
Source: Past IMO shortlisted problem.
Rename $m\to x$ and $n\to y$
We see $x\geq 3$, $y\geq 1$. Modulu 3 implies $x$ is odd. For $x\leq 5$ we get only $(3,1)$, $(5,3)$.
Say $x\geq 6$, then $$3^y\equiv -5\;({\rm mod}\; 64)$$ It is not difficult to see $$3^{11}\equiv -5\;({\rm mod}\; 64)$$ so $3^{y-11}\equiv 1\;({\rm mod}\; 64)$. Let $r=ord_{64}(3)$, then since $\phi(64)=32$, we have (Euler) $$3^{32}\equiv 1\;({\rm mod}\; 64)$$ We know $r\;|\;32$. Since $$3^{32} -1 = (3^{16}+1)\underbrace{(3^8+1)(3^4+1)(3^2+1)(3+1)(3-1)}_{(3^{16}-1)}$$ we get $r=16$ so $16\;|\;y-11$ and thus $y=16k+11$ for some integer $k$.
Look at modulo 17 now. By Fermat little theorem: $$2^x\equiv 3^{16k+11}+5\equiv (3^{16})^k \cdot 3^{11}+5\equiv 1^k\cdot 7+5\equiv 12\;({\rm mod}\; 17)$$ Since $x$ is odd we have \begin{eqnarray*} 2^1&\equiv & 2\;({\rm mod}\; 17)\\ 2^3&\equiv & 8\;({\rm mod}\; 17)\\ 2^5&\equiv & -2\;({\rm mod}\; 17)\\ 2^7&\equiv & -8\;({\rm mod}\; 17)\\ 2^9&\equiv & 2\;({\rm mod}\; 17) \end{eqnarray*} so upper congurence is never fulfiled, so no solution for $x\geq 6$.
Let's rewrite the question a bit, remembering that $5 = 2^5-3^3$ and putting this in the basic equation such that we start with: $$ 2^m -2^5 = 3^n - 3^3 \tag 1$$ $$ { 2^M-1 \over 3^3} = { 3^N-1 \over 2^5} \tag 2$$ $\qquad \qquad \qquad $ where $m=5+M$ and $n=3+N$. For $M=N=0$ this is our largest known solution.
We'll prove now, that assuming $M,N>0$ leads to a contradiction by looking at the primefactorizations of the lhs and rhs. We need Fermat's little theorem about the relation between exponents $M$ and primefactors of $2^M-1$ and more specifically the sometimes so called "lifting-the-Exponent lemma" (LTE). (See my interpretation of this at my homepage)
We now assume $M,N>0$.
First, to have in the numerator in the lhs the factor $3^3$ we need, that $M=2 \cdot 3^2 \cdot x$. Moreover, $x$ is not allowed to have additional primefactors $3$ . This is because once we have more primefactors $3$ in the lhs it can never be equal to the rhs which by construction cannot have the primefactor $3$ in its factorization. So $M$ is at least $M=2 \cdot 3^2 \cdot x$ with $x=1$.
Second, analoguously to have in the numerator in the rhs the factor $2^5$ we need, that $N=2^3 \cdot y$ where $y$ is not allowed to have additional primefactors $2$. (Equivalent reasoning as before)
We can then rewrite this in the basic expression $$ { 2^{2 \cdot 3^2 \cdot x}-1\over 3^3 } \overset?= { 3^{2^3 \cdot y}-1\over 2^5 } \tag 3$$ $\phantom{xxxxxxxxxxxxxxxxxxxxxxxxxxx}$ where $x$ cannot have a factor $3$ and $y$ cannot have a factor $2$.
Let, for a basic idea, $x=y=1$ and let us look whether the equation holds. Factorization of the numerators give $$ { 3^3.7.19.73 \over 3^3 } \overset?= { 2^5.5.41 \over 2^5 } \tag 4 $$
We see, that each numerator has the same factor as the denominator, so the first prerequisite of an equation is satisfied.
But the other primefactors are different - and for instance, in the lhs we need to change the exponent $x$ such that the expression includes the primefactors $5$ and $41$. This can be done by finding the group-order of $5$ and $41$ to base $2$ wich is $o(2,5)=4=2^2$ and $o(2,41)=20=2^2\cdot 5$. The exponent must thus be the $\operatorname{lcm}([2\cdot 3^2,2^2,2^2 \cdot 5])=2^2 \cdot 3^2\cdot 5$.
The analoguous consideration for the rhs means to make sure, that $y$ allows that the primefactors $7,19,73$ are included, which it must reflect the group orders of $7,19,73$ to base $3$ and the exponent must be $\operatorname{lcm}([2^3,6,18,12])=2^3 \cdot 3^2$
Thus we can rewrite the hoped equality
$$
{ 2^{2^2 \cdot 3^2 \cdot 5 \cdot x_1}-1\over 3^3 } \overset?= { 3^{2^3 \cdot 3^2 \cdot y_1}-1\over 2^5 } \tag 5
$$
$\phantom{xxxxxxxxxxxxxxxxxxxxxxxxxxx}$ where $x_1$ cannot have a factor $3$ and $y_1$ cannot have a factor $2$.
Now the numerator of the lhs contains all the so-far-required primefactors - but many more! We'll get for $e_2=2^2 \cdot 3^2 \cdot 5 = 180$ in the numerator of the lhs:
$$\begin{array} {llll} 2^{e_2}-1 &= &(3^3) \\
&&\cdot (7.19.73) \\
&&\cdot (5^2.41) \\
&&\cdot 13.37 \\
&& .11.31.61.109.151.181.331.631.1321.23311.54001.550938219504661
\end{array}
\tag {5.a}$$
Analoguously on the rhs we get with $e_3= 2^3 \cdot 3^2 =72 $ for the numerator
$$ \begin{array} {llll} 3^{e_3}-1 &=& (2^5) \\
&& \cdot (5.41) \\
&& \cdot (7.19.73) \\
&& \cdot 13.37 \\
&& .757.6481.149888744552324233 \phantom{1321.23311.54001.550938219504661}
\end{array} \tag {5.b}
$$
Obviously this is not an equality, and to possibly obtain one we have again to expand the exponents such that both sides have the now visible primefactors equally.
This can of course be done with a computersoftware and can be repeated as far as wished (and possible from numerical largeness)
But already in this next step we get a contradiction. If we want, that the lhs gets also the primefactor $757$ (which occurs in the rhs) then it is required, that the exponent contains the number $756=2^2 . 3^3 . 7$ - but we had from the beginning, that we can only have $3^2$ in the exponent and not $3^3$.
So the requirement of needing the primefactor $757$ in the lhs-numerator requires to have $3^3$ in the exponent. And together with $2^2$ we'll get $3^4$ as factor in that numerator, which when cancelled with the denominator $3^3$ leaves one primefactor $3$ -- which cannot occur in the rhs by construction.
So this is a proof that there is no larger $m,n$ than $m=5$ and $n=3$ such that $2^m=3^n+5$.
P.s.: We had, as far as I remember, related questions here in MSE, checking other differences than $5$ and also with other bases then $2$ and $3$, sometimes I had the procedure to apply 2 or three times recursively to arrive at the contradiction.
(However I lack the time at the moment to look for that duplicates - you can ease the lookup when searching for the two answerers "Will Jagy" and "Gottfried Helms" for the related questions)
Now to have a disproof for the existence of equality we search one prime factor which occurs in the lhs but not in the rhs
