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.
 A: Hint $\rm\displaystyle\ \ 3\ \bigg|\ \frac{f(n+1)}{f(n)}\ \Rightarrow\ 3^k\ \bigg|\ \frac{f(1)}{f(0)}\frac{f(2)}{f(1)}\frac{f(3)}{f(2)}\cdots\frac{f(k)}{f(k-1)}\: =\: \frac{f(k)}{f(0)},\ $ a prototypical telescopy.
A: The last step you did can be corrected as
$$2^{3^{m+1}}+1 = (2^{3^m})^3+1$$ because if you look at it this way
$$(2^{3^m})^3 = (2^{3^m}) \times (2^{3^m}) \times (2^{3^m}) = 2^{3 \times 3^m} = 2^{3^{m+1}}$$   
Using the fact that the result is true for $k=m$
$$2^{3^{m}}+1 = x \times 3^{m} \implies 2^{3^{m}} = x3^{m}-1 \tag{B}$$
$$
\begin{align*}
2^{3^{m+1}} &= (2^{3^m})^3 \\
&= (x3^{m}-1)^3  \\
&= x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1}-1\\
\end{align*}
$$
Which means 
$$2^{3^{m+1}}+1 = x^3 3^{3m}-x^2 3^{2m+1}+x3^{m+1} \tag{A}$$
And clearly $(A)$ shows the right side is divisible by $3^{m+1}$ because each term is divisible by $3^{m+1}$
which means $2^{3^{m + 1}}+1 = y3^{m+1}$ for some $y$, or the result is true for $k=(m+1)$.
A: 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$
A: We  show, as was observed by Sivaram Ambikasaran, that $3^{n+1}$ divides $2^{3^n}+1$.  For $\varphi(3^{n+1})=2\cdot 3^n$.  By Euler's Theorem,  $2^{2\cdot 3^n}\equiv 1\pmod{3^{n+1}}$. Thus $2^{3^n}\equiv \pm 1 \pmod{ 3^{n+1}}$.  But $2^{3^n}\not\equiv 1 \pmod{3}$, so $2^{3^n}\equiv -1\pmod{3^{n+1}}$. 
Remark: It is not hard to show that $2$ is a primitive root of $3^{e}$ for every positive integer $e$. As a consequence, $2^{3^n}+1$ is not divisible by any power of $3$ greater than $3^{n+1}$.
A: Let F(k)= $2^{p^k}+1$ where p is prime and k in a natural number.
Let b be the highest power of p that divides F(k). So, $F(k)=p^bq$ where q is a natural number and (p,q)=1.
$$2^{p^k}=p^bq-1$$ Then,F(k+1)=$ 2^{p^{k+1}}+1 = ({2^{p^k}})^p +1 = (p^bq-1)^p+1 = p^{b+1}(q-pC_2p^{b-1}q^2+...+p^{(bp-b-1)}q) $ which is divisible by $ p^{b+1}$ if b≥1, but is never divisible by $ p^{b+2}$ as (p,q)=1.
$$Now,\ if\ p|({2^{p^r}}+1)\ ,\ i.e.,\ p|((1+1)^{p^r}+1),\ i.e.,\ p|(3+∑p^rC_r)\ where\ 1≤r<p $$ So, p|3 as each of $p^rC_r$ is divisible by p, which implies p=3.
Now F(0)=3, F(1)=$2^3+1=9\ is\ divisible\ by\ 3^1,\ F(2)=2^{3^2}+1= 513\ is \ divisible\ by\ 3^2 .$
So, by mathematical induction, F(k)= $2^{3^k}+1$ is divisible by $3^k$
