# 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.

-
Do you mean $2^{3^{(m+1)}}+1$ in the last step –  Kirthi Raman Mar 14 '12 at 1:50

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.

-

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)$.

-

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$

-

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}$.

-

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$

-