If $n$ is a power of $13$, does $n \mid 5^n + 8^n$? Motivated by this question:

Is it true that if $n$ is a power of $13$, then $n \mid 5^n + 8^n$ ?

The limited data in oeis/A045597 seems to suggest it is true.
The converse does not hold. The first counterexample is $n=114413= 13^2 \cdot 677$.
The data also suggests that

If $n$ is a power of $13$, then $13n$ is the largest power of $13$ that divides $5^n + 8^n$.

Anyone knows proofs or counterexamples for these two observations?
 A: For first one if $n=13^m$ then using LTE lemma power of $13$ in $5^n+8^n$ will be$$v_{13}(5^n+8^n)=v_{13}(13)+v_{13}(n)=m+1$$Therefore $n|5^n+8^n$. Largest power of $13$ that divides $5^n+8^n$ is $m+1$ if $n=13^m$, so second is true.
A: An easy elementary proof without valuation $v_{13}$.
$$(a+b)^{13}=a^{13}+b^{13}+13ab(a^{11}+b^{11})+13(6)(ab)^2(a^9+b^9)+13(22)(ab)^3(a^7+b^7)+13(55)(ab)^4(a^5+b^5)+13(99)(ab)^5(a^3+b^3)+13(132)(ab)^6(a+b)\qquad (1)$$ We use induction.
For $n=1$ one has $5^{13}+8^{13}=13(13)(3260216077)$ so the property is true for $13^1$. Suppose it is true for $13^n$ so $5^{13^n}+8^{13^n}=13^nA$.
It follows from $(1)$
$$(5^{13^n}+8^{13^n})^{13}=5^{13^{n+1}}+8^{13^{n+1}}+13(40)((5^{13^n})^{11}+(8^{13^n})^{11})+….+13(132)(40)^6(5^{13^n}+8^{13^n})$$
Since for $k$ odd we have $(5^{13^n})^k+(8^{13^n})^k=(5^{13^n}+8^{13^n})Q_k(5^{13^n},8^{13^n})$ where the form of the second factor is well known it follows
$$(13^nA)^{13}=5^{13^{n+1}}+8^{13^{n+1}}+13(13^nA)\left[40(Q_{11}(5^{13n},8^{13n})+….+132(40)^6Q_1(5^{13^n},8^{13^n})\right]$$ Thus $$13^{n+1}|5^{13^{n+1}}+8^{13^{n+1}}$$
