$3^n$ does not divide $4^n+5$ for $n\geq 2$ 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.
 A: 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).
A: 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.
A: 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.  
A: 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.
