$3^n$ does not divide $8^n+1$ for $n\geq 4$ Question as in the title : does anyone know how to prove that $3^n$ does not divide $8^n+1$ for $n\geq 4$ or find a counterexample ?
My thoughts : I have checked that this is true for $n\leq 1000$. One can easily show that certain congruence classes are excluded : for example if $n$ is even, then $8^n+1$ is congruent to $2$ modulo $3$ and so it is not divisible by $3$, if $n$ is congruent to $5$ modulo $6$ then $8^n+1$ is congruent to $18$ modulo $27$ and so it is not divisible by $27$, etc.
On the other hand, it is equally easy to show that $8^n+1$ can be made divisible by arbitrarily large powers of $3$, so I'm not sure that the congruence method helps.
 A: Define

$\mathbb v_p(n)$ : The $p$-adic order (valuation) of number $n$ is the number of times $p$ divides $n$. 

Then,

You want to prove that $\mathbb v_3(8^n+1)\lt n$ for all $n\ge 4$.

Notice that:
$$
\mathbb v_3(8^n+1)=\begin{cases}
0, & n\text{ even}\\
2, & n\equiv1,5\pmod{6}\\
3, & n\equiv3,15\pmod{18}\\
4, & n\equiv9,45\pmod{54}\\
\dots\\
k, & n\equiv3^{k-2},5\cdot 3^{k-2}\pmod{2\cdot 3^{k-1}}\\
\dots
\end{cases}
$$
That is, $\mathbb v_3(8^n+1) = k$ for the first time when $n=3^{k-2}$. Hence for $k=n$, 
$$ n\lt 3^{n-2} \implies \mathbb v_3(8^n+1) \lt n  $$
It is easy to see that LHS holds if and only if $n\ge 4$. 
Q.E.D.
A: From the start we can reason that $n$ must be odd since when it's even it's never divisible. $$8^n+1 \equiv (9-1)^n +1 \equiv (-1)^n+1 \equiv 2 \mod 3$$
Now that we know $n$ is odd, we can use the lifting the exponent lemma (LTE), because,
$$v_3(8^n+1) = v_3(8^n-(-1)^n)$$
So we check the criteria for the LTE
$$v_3(8) = v_3(-1) = 0$$
$$v_3(8-(-1))\ge 1$$
So we have,
$$v_3(8^n-(-1)^n) = v_3(n) + v_3(8-(-1))$$
$$v_3(8^n+1) = v_3(n)+2$$
Because our original problem asks to show that $n>v_3(8^n+1)$ for $n\ge 4$, we can plug this result from the LTE into our inequality,
$$n>v_3(n)+2$$
At this point it should be pretty much down hill, but let's write $n=3^t m$ for $v_3(m)=0$ to make it clearer to look at.
$$3^tm>t+2$$
An exponential grows much faster than linear, so it's proven. The only contradictions to this inequality occur for when $n<4$.
