Prove that if $n|5^n + 8^n$, then $13|n$ using induction

Question

I have to prove using mathematical induction that if $n \ge 2$ and $n|5^n + 8^n$, then $13|n$.

Please help me.

Answer 1

Let $p$ be the smallest prime natural number dividing $n$. Clearly, $p$ is odd and $p\neq 5$. Then, $\left(\frac{8}{5}\right)^{2n}\equiv 1\pmod{p}$. Hence, the order of $\frac{8}{5}$ divides $\gcd(2n,p-1)=2$. Therefore, $\left(\frac{8}{5}\right)^2\equiv 1\pmod{p}$, leading to $p=3$ or $p=13$. However, as $\frac{8}{5}\equiv 1\pmod{3}$, this removes the possibility that $p=3$. As a result, $p=13$.

P.S.: For any integer $m$ not divisible by $5$, interpret $\frac{8}{5}\mod m$ as the solution modulo $m$ to the congruence $5x\equiv 8\pmod{m}$. I don't know how to approach this problem by induction.

Answer 2

This is a provisional (correct) answer. I'm now on a possible right road to use induction as requested by the OP. I hope to use induction soon and give another answer (at least for me, this has been revealed somewhat difficult).

Let $$Q_n(a,b)=\frac{a^n+b^n}{a+b}=\sum_{k=0}^{k=n-1}a^k(-b)^{n-1-k}$$ The following elementary property is given in “13 Lectures on Fermat’s Last Theorem” by Paulo Ribenboim. Springer-Verlag. New York Heidelberg Berlin. page 52: $$(Q_n(a,b),a+b)=(n,a+b)\qquad (1)$$ In our case we have $$(Q_n(5,8),13)=(n,13)\qquad (2)$$ Besides if $n|5^n+8^n$ then $n$ is clearly odd. It follows, assuming $n$ odd, $$5^n+8^n=13Q_n(5,8)\qquad (3)$$ Now, if $(n,13)= 1$ then, by $(2)$, $(Q_n(5,8),13)=1$ then, by $(3)$, $n$ does not divide $5^n+8^n$.

It follows that $n$ and $13$ are not coprime hence $n$ is a multiple of the prime $13$ (equivalently $13|n$).

REMARK.- If $13$ divides $5^n+8^n$ then $13^2$ divides $5^n+8^n$. Calculation gives the smallest example $n\gt 1$ for which $n$ divides $5^n+8^n$ is $n=13$; in fact one has $$5^{13}+8^{13}=13^2\cdot 3 260 216 077$$