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

• In other words, you want to prove that $3$-adic valuation of $8^n+1$ is less than $n$ for all $n\ge 4$. Apr 15, 2020 at 13:26
• I think there was a similar question about $3^n$ and $5^n+2$ recently Apr 15, 2020 at 13:26
• @HagenvonEitzen, math.stackexchange.com/questions/3623700/…
– lhf
Apr 15, 2020 at 14:36

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.

• Thanks for the feedback. Can you prove that $\mathbb v_3(8^n+1)=k$ for $n=3^{k-2}$ or is it just a guess ? Apr 15, 2020 at 14:42
• Ah I'm starting to see the pattern : $8^n+1=\frac{8^{2n}-1}{8-1}$, so we just need to compute $\mathbb v_3(8^{2n}-1)$. Also by Fermat's small theorem we have $8^{6n} \equiv 8 (mod\ 6n)$. Apr 15, 2020 at 14:49
• @EwanDelanoy The formula for $\mathbf v_3(8^n+1)$ is based on the generalizing the pattern of what you already observed in your post under "My thoughts". I hope this helps. Apr 15, 2020 at 14:52
• It sure helps. Time will tell if it easily can be turned into a full proof Apr 15, 2020 at 14:53
• @EwanDelanoy Alternatively, you are looking for a rigorous proof that shows: $$\mathbf v_3(2^n+1) =\begin{cases} \mathbf v_3(n) + 1, & n\text{ odd}\\ 0& n\text{ even} \end{cases}$$ Because then the proof is easy: (last "$\lt$" is for $n\ge 4$) $$\mathbf v_3(8^n+1) = \mathbf v_3(2^{3n}+1) \le \mathbf v_3(3n) + 1 = \mathbf v_3(n) + 2\le\log_3n+2\lt n. \square$$ Apr 16, 2020 at 12:29

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

• Ah so what I've observed was actually LTE doing its job. I've never heard of it untill now so thank you for giving it a name. Apr 17, 2020 at 10:51