How can I prove $5^{3^n}+1$ is divisible by $3^{n+1}$ The problem was to prove that $5^{3^n}+1$ is divisible by $3^{n+1}$ for all nonnegative integers. 
I attempted to prove the claim by induction.
Claim: For all $ n \ge 0 $ $$ 3^{n+1} ~|~ 5^{3^n}+1 $$
Basis case:
$$ 3^{0+1} = 3  ~|~ 6 =  5^{3^0} + 1 ~ ~\checkmark$$ 
Inductive step: Assume $$ 3^{k+1} ~|~ 5^{3^k} + 1 $$
It follows by the definition of divides, $ 5^{3^k } + 1 = 3^{k+1}\cdot m $ for some integer $m$.   
Then $$~~~~~ 5^{3^{k+1}} +1
\\   = 5^{3^k \cdot 3 }+1 
\\ = 5^{3 \cdot 3^k}+1  
\\ = \left( 5^3 \right)^{3^k} +1 
\\=  125^{3^k} +1 $$ I have no idea how to proceed. Am I on the right track? If it is possible can I get a hint.
One thing I did notice is that it might be easier to prove $$ 3^{n} ~|~ 5^{3^n}+1 $$ This statement seems to be true, since the basis case is then $1|6$.

Try using the fact that $x^3 +1 = (x+1)(x^2 -x+1).$
