TL;DR How to prove the eight congruences at the end of this post?
Remark. My number theory is rusty and I'm trying to prove the following observations.
Motivation: This result easily implies that $3^n$ does not divide $8^n+1$ for $n\geq 4$, for example, as shown in my suggested answer on the linked question.
Definition. $\mathbb v_p(a)$ = The $p$-adic order of number $a$ is the number of times $p$ divides $a$.
When I start observing congruence classes, it is easy for me to see the initial observations:
$$\begin{array}{}
\mathbf v_3(2^n-1) =\begin{cases} \mathbf v_3(n) + 1, & n\text{ even}\\0, & n\text{ odd} \end{cases} \\
\mathbf v_3(2^n+1) =\begin{cases}0, & n\text{ even}\\ \mathbf v_3(n) + 1, & n\text{ odd} \end{cases}
\end{array}$$
In other words, I've actually observed that:
$$\begin{array}{}
\mathbb v_3(2^n-1)=\begin{cases}
0, & n\equiv1\pmod{2}\\
1, & n\equiv2,4\pmod{6}\\
2, & n\equiv6,12\pmod{18}\\
3, & n\equiv18,36\pmod{54}\\
\dots\\
k, & n\equiv2\cdot3^{k-1},4\cdot 3^{k-1}\pmod{2\cdot 3^{k}}\\
\dots
\end{cases}
\\
\mathbb v_3(2^n+1)=\begin{cases}
0, & n\equiv0\pmod{2}\\
1, & n\equiv1,5\pmod{6}\\
2, & n\equiv3,15\pmod{18}\\
3, & n\equiv9,45\pmod{54}\\
\dots\\
k, & n\equiv1\cdot3^{k-1},5\cdot 3^{k-1}\pmod{2\cdot 3^{k}}\\
\dots
\end{cases}
\end{array}$$
Where notice that when we realize $k-1 = \mathbf v_3(n)$, the initial observations follow.
My question is, how would we formally and rigorously prove these observations?
Below is a possible starting point for the rigorous proof:
It seems to me like a starting point would be to notice that by definition:
$\space\space\space\space$ 1) $k\le\mathbf v_3(2^n\mp1)$ $\iff$ $2^n \pm1\equiv 0\pmod{3^{k}}$
$\space\space\space\space$ 2) $\mathbf v_3(2^n\mp1)\le k$ $\iff$ ${2^n}\pm1\not\equiv 0\pmod{3^{k+1}}$
Where depending on "$\mp$" we have:
$\space\space\space\space$ a) $ n\equiv2\cdot 3^{k-1}\pmod{2\cdot 3^{k}}$ or $ n\equiv4\cdot3^{k-1}\pmod{2\cdot 3^{k}}$
$\space\space\space\space$ b) $ n\equiv1\cdot 3^{k-1}\pmod{2\cdot 3^{k}}$ or $n\equiv5\cdot3^{k-1}\pmod{2\cdot 3^{k}}$
Now we need to prove that:
-
a) implies the RHS of 1) and RHS of 2) for "$-$"
-
b) implies the RHS of 1) and RHS of 2) for "$+$"
After proving that, we would have the implications: LHS $\iff$ RHS.
Finally, LHS of 1) combined with LHS of 2) would imply the observations.
To state the implications:
We can use a corollary of Euler's Theorem to obtain the implications:
a) implies the RHS of 1) and RHS of 2) for "$-$":
$$\begin{array}{}
n \equiv 2\cdot3^{k-1} \quad(\bmod 2\cdot3^{k})
&\implies 2^{n} \equiv 2^{2\cdot3^{k-1}} \quad(\bmod 3^{k+1})
\\
n \equiv 4\cdot3^{k-1} \quad(\bmod 2\cdot3^{k})
&\implies 2^{n} \equiv 2^{4\cdot3^{k-1}} \quad(\bmod 3^{k+1})
\end{array}$$
b) implies the RHS of 1) and RHS of 2) for "$+$":
$$\begin{array}{}
n \equiv 1\cdot3^{k-1} \quad(\bmod 2\cdot3^{k})
&\implies 2^{n} \equiv 2^{1\cdot3^{k-1}} \quad(\bmod 3^{k+1})
\\
n \equiv 5\cdot3^{k-1} \quad(\bmod 2\cdot3^{k})
&\implies 2^{n} \equiv 2^{5\cdot3^{k-1}} \quad(\bmod 3^{k+1})
\end{array}$$
To finish the proof, we have to prove:
$$\begin{array}{}
2^{2\cdot3^{k-1}} \not\equiv +1\quad(\bmod 3^{k+1})
\\
2^{4\cdot3^{k-1}} \not\equiv +1 \quad(\bmod 3^{k+1})
\end{array}$$
$$\begin{array}{}
2^{1\cdot3^{k-1}} \not\equiv -1 \quad(\bmod 3^{k+1})
\\
2^{5\cdot3^{k-1}} \not\equiv -1 \quad(\bmod 3^{k+1})
\end{array}$$
$$\begin{array}{}
2^{2\cdot3^{k-1}} \equiv +1\quad(\bmod 3^{k})
\\
2^{4\cdot3^{k-1}} \equiv +1 \quad(\bmod 3^{k})
\end{array}$$
$$\begin{array}{}
2^{1\cdot3^{k-1}} \equiv -1 \quad(\bmod 3^{k})
\\
2^{5\cdot3^{k-1}} \equiv -1 \quad(\bmod 3^{k})
\end{array}$$
But I'm not sure how to prove these eight congruences.
Best Answer
Equivalences for Induction
Since $2^6\equiv1\pmod9$, we have $$ \begin{align} 2^{6m+1}+1&\equiv3\pmod9\tag1\\ 2^{6m+2}-1&\equiv3\pmod9\tag2\\ 2^{6m+4}-1&\equiv6\pmod9\tag3\\ 2^{6m+5}+1&\equiv6\pmod9\tag4\\ \end{align} $$
If $n$ is even, $n\in\{0,2,4\}\pmod6$, $2^{2n}+2^n+1\equiv3\pmod9$ and $$ \left(2^{2n}+2^n+1\right)\left(2^n-1\right)=\left(2^{3n}-1\right)\tag5 $$ If $n$ is odd, $n\in\{1,3,5\}\pmod6$, $2^{2n}-2^n+1\equiv3\pmod9$ and $$ \left(2^{2n}-2^n+1\right)\left(2^n+1\right)=\left(2^{3n}+1\right)\tag6 $$
Applying the Equivalences
Let $P(k)$ be the statement that $v_3(n)=k\implies v_3\!\left(2^n-(-1)^n\right)=k+1$.
$P(0)$ is verified by $(1)-(4)$.
$P(k)\implies P(k+1)$ is verified by $(5)-(6)$.
Therefore, $$ \bbox[5px,border:2px solid #C0A000]{v_3\!\left(2^n-(-1)^n\right)=v_3(n)+1}\tag7 $$