<s>[INST] Show that $2^{3^k}+1$ is divisible by $3^k$ for all positive integers $k$ I attempted this by induction: Here is what I did
For $k=1, 2^{3^{1}}+1 = 2^{3}+1 = 9 = 3^{2}$ is divisible by $3^{1}$ , so the result is true for $k=1$
Now I assume the result to be true for $k=m$, 
$2^{3^{m}}+1$ is divisible by $3^m$. To show the result to be true for $k=(m+1)$,
$2^{3^{m+1}}+1 = 2^{3^m} \times 2^3+1$ and I was stuck here.
 [/INST] Note that $2^{3^{m+1}}+1 = \left(2^{3^m} \right)^3 + 1 = \left(2^{3^m} + 1 \right)\left(\left(2^{3^m} \right)^2 - 2^{3^m} + 1 \right)$. By induction hypothesis, $3^m$ divides $\left(2^{3^m} + 1 \right)$. All you need to show is that $3$ divides $\left(\left(2^{3^m} \right)^2 - 2^{3^m} + 1 \right)$.
Hint: $2^{3^m} \equiv -1 (\bmod 3)$.
In-fact, proceeding along the same lines as you have done you can show that $3^{k+1}$ divides $2^{3^k}+1$
</s>