The exact power of 3 dividing 2^(3ⁿ) + 1

Idea. Each cube multiplies the number $x+1$ by a factor having valuation exactly $1$.

Lemma. If $x\equiv-1\pmod3$, then $v_3(x^2-x+1)=1$. Indeed write $x=3t-1$: then
$$x^2-x+1=9t^2-6t+1-3t+1+1=9t^2-9t+3\equiv3\pmod9,$$
so $3\mid x^2-x+1$ but $9\nmid x^2-x+1$.

Induction. Let $x_n=2^{3^n}$. As $3^n$ is odd, $x_n\equiv(-1)^{3^n}=-1\pmod3$, so the lemma applies to $x_n$.
- $n=0$: $x_0+1=3$, so $v_3=1$.
- Step: $x_{n+1}+1=x_n^3+1=(x_n+1)(x_n^2-x_n+1)$, so
$$v_3(x_{n+1}+1)=v_3(x_n+1)+1.$$

Hence $v_3(x_n+1)=n+1$.

Check. $2^3+1=9$ ($v_3=2$), $2^9+1=513=27\cdot19$ ($v_3=3$), $2^{27}+1=134217729=81\cdot1657009$ ($v_3=4$).

Remark. This is the special case of the *Lifting The Exponent lemma*: for an odd prime $p$ with $p\mid a-b$, $p\nmid ab$: $v_p(a^n-b^n)=v_p(a-b)+v_p(n)$.

Lesson. To compute an exact $p$-adic valuation, factor with the cyclotomic identity ($x^p-y^p$ or $x^p+y^p$) and track how the valuation grows at each step.