Show that for every $n \geq 0 \in \mathbb{N}$, $3^{n+1}|(2^{3^n}+1)$ (in addition, I must use proof by induction, strong induction, or minimum counterexample).
Initially, I thought that normal induction would be enough. To simplify the problem, I tried letting $3^n = k$ and then prove for every $k$, except I couldn't get it to work (plus I'm not sure if that is entirely "accurate," that is whether or not I have to prove this for just the $k$s that are a power of $3$). I also tried to rearrange $2^{3^{n+1}}+1$ so that it would have a factor of $3^{n+2}$ in all terms (using the assumption that $2^{3^n}+1$ is divisible by $3^{n+1}$), but got nowhere. For the same reasons, strong induction also failed to work out, but I still suspect that I just need to rearrange the terms correctly.
I appreciate all and any help. Thank you kindly!
Let $P(n) \equiv 3^{n+1} \mid (2^{3^n}+1)$
$P(0)$ is true since $3 \mid 3$.
Suppose $P(k)$ is true for some $k \in [0..\infty)$.
We need to demonstrate that this implies $P(k+1)$ is true.
$2^{3^{k+1}}+1 = \left( 2^{3^k} \right)^3 + 1 = \left(2^{3^k}+1 \right) \left( \left( 2^{3^k} \right)^2 - 2^{3^k} + 1 \right)$
We note that, by hypothesis, $3^{k+1} \mid 2^{3^k}+1$. If we can demonstrate that $3 \mid \left( 2^{3^k} \right)^2 - 2^{3^k} + 1$, then it will follow that $3^{k+2} \mid (2^{3^{k+1}}+1)$; that is to say P(k+1) is true, and we will be done.
We demonstrate below that $3 \mid \left( 2^{3^k} \right)^2 - 2^{3^k} + 1$
Note that $3^k$ is an odd number for all $k \in [0..\infty)$. Computing modulo $3$, we find
\begin{align} \left( 2^{3^k} \right)^2 - 2^{3^k} + 1 &\equiv \left( (-1)^{3^k} \right)^2 - (-1)^{3^k} + 1 \pmod 3\\ &\equiv (-1)^2 - (-1) + 1 \pmod 3\\ &\equiv 1 + 1 + 1 \pmod 3\\ &\equiv 0 \pmod 3\\ \end{align}