$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.

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).
