3
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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 ? $\endgroup$ Apr 15, 2020 at 14:42
  • $\begingroup$ 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)$. $\endgroup$ Apr 15, 2020 at 14:49
  • $\begingroup$ @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. $\endgroup$
    – Vepir
    Apr 15, 2020 at 14:52
  • $\begingroup$ It sure helps. Time will tell if it easily can be turned into a full proof $\endgroup$ Apr 15, 2020 at 14:53
  • $\begingroup$ @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$$ $\endgroup$
    – Vepir
    Apr 16, 2020 at 12:29
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vepir
    Apr 17, 2020 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.