$$\\$$Em minha apostila tem as demonstrações dos seguintes lemas:$$\text{Lema (*): Sejam $a,m,n,q,r\in\mathbb{N}$ com $a\geq2$ tais que $m=nq+r$ then:}\\(a^m-1,a^n+1)=\begin{cases}(a^n+1,a^r-1)& \text{Se}\;q\;\text{é par}\\ (a^n+1,a^r+1)& \text{Se}\;q\;\text{é ímpar}\end{cases}$$ Outro lema: $$\text{Lema (**):}\;\;(x,y)=x\Longleftrightarrow x\mid y$$
A questão é a seguinte: Seja $(M_n)_n$ a sequência definida por $M_n=2^n-1$. Mostre que $3\mid M_n$ se, e somente se, $n$ é par. $$$$Demonstração:
$\Longrightarrow$
$3\mid 2^n-1\underbrace{\Longrightarrow}_{**} (2^n-1,3)=3\Longrightarrow (2^n-1,2+1)=3$
Pelo lema (*), e sabendo que $\underbrace{n=1n+0}_{m=nq+r}$ temos que:
Se $n$ é ímpar, então $(2^n-1,2+1)=(2+1,2^0+1)=(3,2)=1\neq3$ então temos que se $n$ é ímpar $3\nmid 2^n-1$.
Se $n$ é par, então $(2^n-1,2+1)=(2+1,2^0-1)=(3,0)=3$ então temos que se $n$ é par, então $3\mid 2^n-1$.
Logo, se $3\mid 2^n-1\Longrightarrow n$ é par. $\;\;\;\;\;\Box$
$\Longleftarrow$
Tendo que $n$ é par, então $n=2k$ para algum $k\in\mathbb{N}$
Vamos mostrar então que $3\mid 2^{2k}-1\Longrightarrow 3\mid4^k-1\;\;\;\forall k\in\mathbb{N}$.
Demonstrando por indução:
I) $k=0$$$3\mid 4^0-1\Longrightarrow 3\mid 0\;\;\;\;\;\;\text{OK}$$
II) Hipótese: $$3\mid4^k-1$$
III) Tese: $$3\mid4^{k+1}-1$$
Demonstração:
$$3\mid4^{k+1}-1\\3\mid4^k4-1\\3\mid4^k4-1-3+3\\3\mid4^k4-4+3\\3\mid4(4^k-1)+3$$ Por Hipótese de indução $3\mid4^k-1$ então $3\mid4(4^k-1)$ e como $3\mid 3$ logo $3\mid 4^{k+1}-1$ $\forall k\in\mathbb{N}\;\;\;\;\;\;\Box$
We use congruence notation. Note that $2\equiv -1\pmod{3}$.
If $n$ is even, then $2^n-1\equiv (-1)^n-1\equiv 1-1\equiv 0\pmod{3}$. Thus $3$ divides $2^n-1$.
If $n$ is odd, then $2^n-1\equiv (-1)^n-1\equiv -2\equiv 1\pmod{3}$. Thus $3$ does not divide $2^n-1$.
Remark: Your proof is correct. It is longer than necessary.
One can prove the result in various other ways. For example, recall that if $n$ is odd, then $$x^n+1=(x+1)(x^{n-1}-x^{n-2}+\cdots+1).$$ Putting $x=2$, we find that $3$ divides $2^n+1$, and therefore the remainder when you divide $2^n-1$ by $3$ is $2$.
Now we deal with even $n$. If $n$ is even and $\gt 0$, then $n-1$ is odd. Therefore by the previous calculation $2^{n-1}-1$ has shape $3m+2$. But then $$2^n-1=2(2^{n-1}-1)+1=2(3m+2)-1=6m+3,$$ so $2^n-1$ is divisible by $3$.