Proof that $3^n | 2^{3^n} + 1$

Question

Question:

Proof by induction that $3^n | 2^{3^n} + 1$.

Attempt: $$ 2^{3^{n+1}} + 1 = 2^{3^n} 2^3 + 1 = 2^{3^n} 2^3 + 1 + 2^3 - 2^3 = 2^3( 2^{3^n} + 1 ) + 1 -2^3$$

And the first is $3^n |$ but second I don't know how to proof that.

Answer 1

$$2^{3^m}+1=h\cdot 3^{m}\implies 2^{3^{m+1}}+1=(h\cdot 3^m-1)^3+1=\\=(h\cdot 3^m)((h\cdot 3^{m}-1)^2-(h\cdot 3^m-1)+1)=\\=(h\cdot 3^m)(h^2\cdot 3^{2m}-3h\cdot 3^m+3)$$ if $m\ge 1$, then $3$ divides $h^2\cdot3^{2m}-3h\cdot 3^m+3$

Answer 2

Hint: Use the fact that $$(2^{3^n})^3 + 1 = \left(2^{3^n} +1\right) \left((2^{3^n})^2- 2^{3^n} + 1\right)$$

Answer 3

Hint: you should be looking at $2^{3^{n+1}}$, not $2^{3^n+1}$. Assume, by induction that $2^{3^n} + 1 = 3^nd$, i.e., $2^{3^n} = 3^nd - 1$, and see what you can get from $2^{3^{n+1}} + 1 = 2^{3^n\cdot 3} + 1 = (2^{3^n})^3 + 1$.

Answer 4

$$2^{3^{n+1}}+1 = (2^{3^n})^3 + 1 = (2^{3^n}+1)((2^{3^n})^2 - 2^{3^n} + 1).$$ Can you take it from there?