$3^n$ does not divide $8^n+1$ for $n\geq 4$

Question

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.

Answer 1

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

Answer 2

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.