# Is $2^{3^n}+1$ always divisible by $3^{n+1}$?

Because it certainly seems to be the case for all positiv $n$ but how can I prove it?

• I guest you can prove it by using the recurrence relation. Jul 20, 2014 at 21:38

## 2 Answers

Proof by induction: For $n=1$ it is true. Now assume $2^{3^n}\equiv -1(\text { mod }3^{n+1})$, then $$2^{2\cdot3^n}-2^{3^n}+1\equiv ({-1})^2-(-1)+1\equiv 0 (\text { mod }3)$$ so $3|2^{2\cdot3^n}-2^{3^n}+1$ and $3^{n+1}|2^{3^n}+1$, so $$3^{n+2}|(2^{3^n}+1)(2^{2\cdot3^n}-2^{3^n}+1)=2^{3^{n+1}}+1$$

Suppose

$$2^{3^n} + 1 \equiv 0 \pmod{3^{n+1}}$$

Then

$$2^{3^n} \equiv -1 + 3^{n+1} a \pmod{3^{n+2}}$$

for some value of $a$. And thus

\begin{align}2^{3^{n+1}} &\equiv \left(-1 + 3^{n+1} a\right)^3 \\&\equiv (-1)^3 + 3 \cdot (-1)^2 \left(3^{n+1} a \right) + \ldots \\&\equiv -1 + 3^{n+2}(\ldots) + \ldots \\&\equiv -1 \pmod{3^{n+2}} \end{align}

In fact, we can show more: that $3^{n+2}$ does not divides $2^{3^n}-1$. Repeating a similar inductive argument, if:

$$2^{3^n} \equiv -1 + 3^{n+1} a \pmod{3^{n+3}}$$

for some $a$ such that $a \not\equiv 0 \pmod{3}$, then we ave

$$2^{3^{n+1}} \equiv -1 + 3^{n+2} a \pmod{3^{n+3}}$$

and so we know that $3^{n+2}$ divides $2^{3^{n+1}} + 1$, but $3^{n+3}$ does not.