$3^n$ does not divide $4^n+5$ for $n\geq 2$

Question

Question as in the title : does anyone know how to prove that $3^n$ does not divide $4^n+5$ for $n\geq 2$ or find a counterexample ?

My thoughts : (1) I have checked that this is true for $n\leq 1000$.

(2) I asked a similar question recently, and it was successfully solved with a method that uses a "lifting exponent lemma" which ultimately reduces to the identity $x^k-y^k=(x-y)(x^{k-1}+x^{k-2}y+\ldots+y^{k-1})$. Since $4^n+5$ cannot be so factored, this does not seem to apply here.

(3) For $r\geq 0$, denote by $q_r$ the smallest positive integer such that $4^{q_r}+5$ is divisible by $3^r$. It is easy to see that the order of $4$ modulo $3^r$ is exactly $3^{r-1}$, and hence $3^r$ divides $4^n+5$ iff $n\equiv q_r \ \pmod{3^{r-1}}$. It follows that $q_{r+1}\equiv q_r \ \pmod{3^{r-1}}$ and so we have a decomposition in base three, $q_r=\sum_{j=0}^{r-1}\varepsilon_j 3^j$ (where $\varepsilon_0=q_0$ and $\varepsilon_k=\frac{q_k-q_{k-1}}{3^{k-1}}\in\lbrace 0,1,2\rbrace$ for $k\geq 1$). The first terms of the $\varepsilon$ sequence are

$$ \varepsilon_0=1,\varepsilon_1=2, 2, 1, 1, 0, 0, 2, 1, 0, 0, 0, 1, 1, 2, 0, 0, 1, 2 $$ No pattern seems to emerge at this point.

Answer 1

Partial answer:

Suppose that for some natural $k>2$ that $3^k\mid4^k+5$; that is, there exists a positive integer $a$ such that $4^k+5=a\cdot3^k$. Notice that for a positive integer $s$, $$4^{k+s}+5=4^s(a\cdot3^k-5)+5=a\cdot3^k4^s-5(4^s-1).$$ Writing $4^{k+s}+5=b\cdot3^{k+s}+c$ for some positive integer $b$ and some integer $c<3^{k+1}$, it follows that $$c=3^k(a\cdot4^s-b\cdot3^s)-5(4^s-1).$$ Thus $3^k\mid4^k+5$ can have more than one solution only if $c=0$; that is, $$\frac{a\cdot4^s-b\cdot3^s}5=\frac{4^s-1}{3^k}$$ for all $s$. One criterion is that $5\mid b\cdot2^s-a$ as derived from the LHS.

This also explains the progressively sparse nature of solutions should more than one exist. LTE gives $$\nu_3(4^s-1)=1+\nu_3(s)\ge k,$$ so $\nu_3(s)\ge k-1$. If $k_0:=k$ is a solution then $k_1$, the solution nearest to $k$ must be of the form $k+r_1\cdot3^{k-2+t_1}$ with $r_1,t_1>0$. Iterating, the sequence of solutions $\{k_i\}_{i\in\Bbb N}$ satisfy the recurrence relation $$k_i=k_{i-1}+r_i\cdot3^{k_{i-1}-2+t_i}$$ with $r_i,t_i>0$ for all $i>0$. Of course, this grows incredibly fast.

Answer 2

For what it's worth. I like to check for patterns. For $n$ up to a million and and a half, I printed out only when the 3-adic valuation of $4^n + 5$ increased, i.e. set a new record.

---

n   n+2   v_3(4^n + 5)   log(n)
4  6 = 2 * 3    2  1.38629
7  9 = 3^2    3  1.94591
25  27 = 3^3    4  3.21888
52  54 = 2 * 3^3    5  3.95124
133  135 = 3^3 * 5    8  4.89035
4507  4509 = 3^3 * 167    9  8.41339
11068  11070 = 2 * 3^3 * 5 * 41    13  9.31181
542509  542511 = 3^3 * 71 * 283    14  13.204
2136832  2136834 = 2 * 3^3 * 7 * 5653    15  14.5748
n          n+2                  v_3(4^n + 5)   log(n)

============================

When a new record is set, the new exponent of $3$ is, roughly, comparable to $\log n$ and eventually much, much smaller than $n$ itself.

==========================

I have now started a run for $n$ up to 1,234,567,890. At some point it will become clear that merely storing the huge number is slowing the computer to uselessness and I will stop it.

Answer 3

(Not a full proof yet) - If a counter-example exists, it must be $n\gt10^{10}$, so far.

Also, if $n_0$ is a counter-example, the next one is $\ge 3^{n_0-1}$, due to $\gamma_k$ sequence.

---

TL;DR I'll try to formalize my observation on your previous question and apply it here. But unlike your previous question, here we cannot factor the expression nicely. Consequently, instead of a direct closed form, we get a "nontrivial" set of recurrences $a_k,b_k,c_k$ that determine $v_3$.

To prove that no counter-examples exist, we must prove an upper bound on $a_k$ or $c_k$.

---

We inductively sieve $3$ congruence classes at every step $k$:

$$n\equiv n^{(k)}_1,n^{(k)}_2,n^{(k)}_3 \pmod{3^k}$$

We have $v_3(4^n+5)=k$ for $n\equiv n^{(k)}_1,n^{(k)}_{2}$ and $v_3(x_n)\gt k$ for $n\equiv n^{(k)}_3$.

Denote $a_k, b_k, c_k=n^{(k)}_1,n^{(k)}_2,n^{(k)}_3$ and notice that WLOG $a_k\lt b_k$.

This gives that $v_3(4^n+5)=k$ for the first time when $n= a_{k}$, giving:

$$ k\lt a_k \implies v_3(4^n+5)\lt k $$

We have $k=n$, and hence need to show that $k\lt a_k$ for all $k\gt k_0=2$.

In other words, we have that $v_3(4^n+5)$ is given by:

$$v_3(4^n+5)= \begin{cases} 1, & n\equiv 0,2 \pmod{3^1}\\ \dots\\ k, & n\equiv a_k,b_k \pmod{3^k}\\ \dots \end{cases}$$

If we start to sieve the congruences, we obtain the congruence classes:

$$ \begin{array}{c|ccc|ccc|ccc} k & &a_k& & &b_k& & &c_k& \\\hline 1 & 0 &=&0+0\cdot3^0 & 2 &=&0+2\cdot3^0 & 1 &=&0+1\cdot3^0 \\ 2 & 1 &=&c_1+0\cdot3^1 & 4 &=&c_1+1\cdot3^1 & 7 &=&c_1+2\cdot3^1 \\ 3 & 7 &=&c_2+0\cdot3^2 & 16 &=&c_2+1\cdot3^2 & 25 &=&c_2+2\cdot3^2 \\ 4 & 25 &=&c_3+0\cdot3^3 & 79 &=&c_3+2\cdot3^3 & 52 &=&c_3+1\cdot3^3 \\ 5 & 52 &=&c_4+0\cdot3^4 & 214 &=&c_4+2\cdot3^4 & 133 &=&c_4+1\cdot3^4 \\ 6 & 376 &=&c_5+1\cdot3^5 & 619 &=&c_5+2\cdot3^5 & 133 &=&c_5+0\cdot3^5 \\ 7 & 862 &=&c_6+1\cdot3^6 & 1591&=&c_6+2\cdot3^6 & 133 &=&c_6+0\cdot3^6 \\ 8 & 133 &=&c_7+0\cdot3^7 & 2320&=&c_7+1\cdot3^7 & 4507&=&c_7+2\cdot3^7 \\ 9 & 4507&=&c_8+0\cdot3^8 & 17629&=&c_8+2\cdot3^8 & 11068&=&c_8+1\cdot3^8 \\ 10 & 30751&=&c_{9}+1\cdot3^{9} & 50434&=&c_{9}+2\cdot3^{9} & 11068&=&c_9+0\cdot3^{9} \\ 11 & 70117&=&c_{10}+1\cdot3^{10} & 129166&=&c_{10}+2\cdot3^{10} & 11068&=&c_{10}+0\cdot3^{10} \\ 12 & 188215&=&c_{11}+1\cdot3^{11} & 365362&=&c_{11}+2\cdot3^{11} & 11068&=&c_{11}+0\cdot3^{11} \\ 13 & 11068&=&c_{12}+0\cdot3^{12} & 1073950&=&c_{12}+2\cdot3^{12} & 542509&=&c_{12}+1\cdot3^{12} \\ 14 & 542509&=&c_{13}+0\cdot3^{13} & 3731155&=&c_{13}+2\cdot3^{13} & 2136832&=&c_{13}+1\cdot3^{13} \\ 15 & 2136832&=&c_{14}+0\cdot3^{14} & 6919801&=&c_{14}+1\cdot3^{14} & 11702770&=&c_{14}+2\cdot3^{14} \\ 16 & 26051677&=&c_{15}+1\cdot3^{15} & 40400584&=&c_{15}+2\cdot3^{15} & 11702770&=&c_{15}+0\cdot3^{15} \\ 17 & 54749491&=&c_{16}+1\cdot3^{16} & 97796212&=&c_{16}+2\cdot3^{16} & 11702770&=&c_{16}+0\cdot3^{16} \\ 18 & 11702770&=&c_{17}+0\cdot3^{17} & 269983096&=&c_{17}+2\cdot3^{17} & 140842933&=&c_{17}+1\cdot3^{17} \\ 19 & 140842933&=&c_{18}+0\cdot3^{18} & 528263422&=&c_{18}+1\cdot3^{18} & 915683911&=&c_{18}+2\cdot3^{18} \\ 20 & 915683911&=&c_{19}+0\cdot3^{19} & 2077945378&=&c_{19}+1\cdot3^{19} & 3240206845&=&c_{19}+2\cdot3^{19} \\ 21 & 3240206845&=&c_{20}+0\cdot3^{20} & 10213775647&=&c_{20}+2\cdot3^{20} & 6726991246&=&c_{20}+1\cdot3^{20} \\ \dots &&\dots&& &\dots&& &\dots& \end{array}$$

And so on...

$$ \begin{array}{c|c|c|c} k &a_k=c_{k-1}+\alpha_k\cdot3^{k-1} & b_k=c_{k-1}+\beta_k\cdot3^{k-1} & c_k=c_{k-1}+\gamma_k\cdot3^{k-1} \\ \end{array}$$

Where we do see that $a_k,b_k,c_k$ grow much faster than $k$.

To prove this fact, we need to observe the $\gamma_k\in\{0,1,2\}$ multipliers in the $c_k$ column, because that column determines the record values.

It appears that the runs of consecutive zeroes $\gamma_k=0$ are extremely sparse (much shorter) compared to the growth of $3^k$, hence there should be no solutions other than $n=1$.

$$\gamma_k=1,2,2,1,1,0,0,2,1,0,0,0,1,1,2,0,0,1,2,2,1,\dots$$

But, at the moment, I'm not sure how to actually prove this observation for all $n$.

The first $21$ terms of $a_k,b_k,c_k$ in the table already give a large bound: If a counter-example exists, it must be at least $n\gt2\cdot 10^{10}$. (at least twice the size of the last $c_k$)

Answer 4

It's a little late here, but hopefully I can shed some light on why I think this is hard or impossible. Looking mod 9 for counterexamples, we can expand the binomial

$$f(n)=5+(1+3)^n = 5+\sum_{k\ge 0}3^k \binom{n}{k} \equiv 5+1+3n = 3(2+n) \mod 9$$

So the only cases we need to consider are when $n\equiv 1 \mod 3$, in other words $n \in 1+3\mathbb{Z}_3$, otherwise it's only divisible by 3 a single time.

First, all $|\cdot|$ in my post are the 3-adic absolute value. Let's reformulate the original question to be $|f(n)|\le 3^{-n}$ as the condition for there to be a counterexample. This suggests to me as $n$ gets larger, we are approaching a root o $f$, and since $f$ can be extended to be a continuous function of $\mathbb{Z}_3$, seen by its Mahler series above let's do that. We can directly solve for a root of $f(x)=4^x+5=0$, since both 4 and -5 are in the region of convergence of the logarithm power series,

$$r = \frac{\ln (-5)}{\ln(4)} \approx $$

1 + 2*3 + 2*3^2 + 3^3 + 3^4 + 2*3^7 + 3^8 + 3^12 + 3^13 + 2*3^14 + 3^17 + 2*3^18 + 2*3^19 + 3^20 + 2*3^22 + 2*3^23 + 3^24 + 3^26 + 2*3^28 + 2*3^29 + 3^31 + 3^32 + 3^36 + 2*3^38 + 3^39 + 3^40 + 2*3^41 + 2*3^42 + 3^44 + 2*3^45 + 2*3^46 + 2*3^48 + O(3^49)

This is the output from the PARI/GP calculator for the input log(-5+O(3^50))/log(4+O(3^50)) I arbitrarily picked about 50 digits of accuracy, but you can get many more without any trouble. The digits of this seems to match your $\varepsilon$ and $\gamma$ sequence mentioned in the question and an answer earlier exactly.

This root is also in $1+3\mathbb{Z}_3$ so it should be near other $n$ by continuity. Let's represent the difference $|r-n|=|h|$, and now write $|f(n)|$ a new way with this root $f(r)=0$.

$$|f(n)| = |f(r)-f(n)| = |4^r-4^n| =|4^n||4^h-1|= \left| \sum_{k\ge 1}3^k\binom{h}{k}\right|$$

$$|f(n)| = \left| 3h \sum_{k\ge 1}\frac{3^{k-1}}{k}\binom{h-1}{k-1}\right|=3^{-1}|h|$$

The series $\sum_{k\ge 0}\frac{3^k}{k+1}\binom{h-1}{k}=\underline{1}+\frac{3}{2}\binom{h-1}{1}+\frac{3^2}{3}\binom{h-1}{2}+\cdots$ has 3-adic absolute value 1 because all binomial terms necessarily have $|\binom{h-1}{k}|\le 1$ and the exponent on $3$ makes all further terms after the first $1$ smaller than the rest, and by ultrametric inequality overtakes.

Now let's combine what we've gained with our reformulation $$|f(n)|= 3^{-1}|r-n| \le 3^{-n}$$

$$|r-n| \le 3^{-n+1}$$

What this says is for there to be a counterexample, $n$ must have all $n-1$ its first 3-adic digits in common with $\frac{\ln (-5)}{\ln(4)}$ in order to be a counterexample. But since $n$ is a natural number, we know its digits after its first $\lfloor \log_3(n)\rfloor$ digits are all $0$. This means in order for a counterexample to exist, there must be a very long string of $n-1-\lfloor \log_3(n)\rfloor$ consecutive $0$s somewhere in the digit expansion of $\frac{\ln (-5)}{\ln(4)}$. I think this is likely irrational and the problem is just as difficult as trying to find a string of repeating digits in say $\sqrt{2}$ in some sort of predictable way, so I doubt it's possible.

Answer 5

This follows from an effective abc conjecture. If $4^n+5=3^nm$ then the quality of this $(a,b,c)$-triple is \begin{align*} q(4^n,5,3^nm)&=\frac{\log(3^nm)}{\log(\mathrm{rad}(4^n\cdot5\cdot3^nm))}\geq\frac{\log(4^n+5)}{\log(30m)}=\frac{\log(4^n+5)}{\log(30)+\log(4^n+5)-\log(3^n)} \end{align*} which is larger than 2 for $n\geq9$, larger than 3 for $n\geq20$, and larger than 4 for $n\geq58$. Conjecturally, there are no such $(a,b,c)$-triples.

---

Below is an unrelated attempt to figure out what's going on algebraic-number-theoretically.

---

In the ring of integers $\mathbb{Z}[\sqrt{-5}]$, we have the factorization of ideals $$(4^n+5)=(2^n+\sqrt{-5})(2^n-\sqrt{-5}).$$ Let $I=(2^n+\sqrt{-5})$ and let $I^\prime=(2^n-\sqrt{-5})$. Note that $(2\sqrt{-5})\subseteq I+I^\prime$. Then $I+I^\prime$ divides both $(2\sqrt{-5})$ and $(4^n+5)$. However, $(2\sqrt{-5})$ has norm $20$ and $(4^n+5)$ has norm $(4^n+5)^2$ (which is coprime to $20$. Thus, $I+I^\prime=1$ which shows that $I$ and $I^\prime$ are coprime.

Now suppose that $4^n+5$ is divisible by $3^n$. We have the factorization of ideals $$(3^n)=(3,1+\sqrt{-5})^n(3,1-\sqrt{-5})^n$$ where $\mathfrak p=(3,1+\sqrt{-5})$ and $\mathfrak q=(3,1-\sqrt{-5})$ are conjugate prime ideals of $\mathbb{Z}[\sqrt{-5}]$. Since $I$ and $I^\prime$ are coprime, exactly one of the two possibilities holds:

• $\mathfrak p^n$ divides $I$ and $\mathfrak q^n$ divides $I^\prime$
• $\mathfrak q^n$ divides $I$ and $\mathfrak p^n$ divides $I^\prime$

The first case occurs when $n$ is even ($\mathfrak p$ contains both $2^n+\sqrt{-5}$ and $1+\sqrt{-5}$ so $\mathfrak p$ contains $2^n-1$ so $3\bigm|2^n-1$ so $n$ is even). The second case occurs when $n$ is odd ($\mathfrak p$ contains both $2^n-\sqrt{-5}$ and $1-\sqrt{-5}$ so $\mathfrak p$ contains $2^n+1$ so $3\bigm|2^n+1$ so $n$ is odd).

Answer 6

Try this, but please check it carefully. I guess it brings us no closer to a conclusive statement, and perhaps is just a rephrasing of every other answer.

You ask whether $3^n|(4^n+5)$ ever happens except when $n=1$. Thus you’re asking whether $v_3(4^n+5)=m\ge n$, and we want to show this is impossible.

Well, if it does happen, then $v_3\bigl(4^n-(-5)\bigr)=m$, i.e. $4^n=-5+3^mu$ with $u\in\Bbb Z_3^\times$.

Now I call in the assistance of the logarithm, $\ln(z)$, given by the series formula you know from Calculus, valid for $z\in1+3\Bbb Z_3$, which fortunately happens for both $4$ and $-5$, as well as, of course, $4^n$. From what you know about the logarithm, we see: \begin{align} \ln(4^n)=n\ln(4)&=\ln(-5)+3^mu'&(u'\in\Bbb Z_3^\times)\\ n&=\frac{\ln(-5)}{\ln(4)}+3^{m-1}u''&(u''=3u'/\ln(4)\in\Bbb Z_3^\times)\,, \end{align} because $v_3(\ln(4))=1$. We might as well call $\ln(-5)/\ln(4)=\lambda$.

But wait. This would be saying that $\lambda$ and $n$ agree in their first $m-1$ ternary digits. But $n$ doesn’t have that many digits, it has only roughly $\log_3(n)$ digits. All that remains to check is that $\lambda$ does not have a huge run of zeros in its ternary expansion, which certainly seems more than plausible, and is well beyond my capabilities.