<s>[INST] For which ${n \in \mathbb{Z}^+_0}$ is the number ${2^n - 1}$ divisible by 7? This is how far I've gotten:
Let ${n=3k+r}$, where ${r=0,1}$ or $2$ (since ${0 \le r < 3}$).
Case ${r=0}$:
\begin{equation}
\begin{aligned}
2^{3k} &\equiv_7 1\\
\Rightarrow 2^{3k}-1 &\equiv_7 0\\
k &\in \mathbb{Z}^+_0\\
\end{aligned}
\end{equation}
For cases ${r=1}$ and ${r=2}$:
\begin{equation}
\begin{aligned}
2^{3k+r}-1 &\equiv_7 0\\
\Leftrightarrow 2^{3k} \cdot 2^r -1 &\equiv_7 0\\
\end{aligned}
\end{equation}
which gives
\begin{equation}
\begin{aligned}
2^0-1=0 &\equiv_7 0\\
2^1-1=1 &\equiv_7 1\\
2^2-1=3 &\equiv_7 3\\
\end{aligned}
\end{equation}
I know (by more or less messing around) that ${r=0,3}$ or $6$ for ${k \in \mathbb{Z}^+_0}$, but I'm getting nowhere in trying to prove it. And I'm not sure how $r$ actually can be 3 or 6 since $r$ should be smaller than 3. Right?
Any hints or guidings towards the right answer would be much appreciated. Thanks!
 [/INST] Bear in mind if $a \equiv 1$ then $a\times k \equiv 1 \times k \equiv k$ and $a^m \equiv 1^m \equiv 1$.
So as you have figured we can writ any $n$ as $n = 3k + r$ where $r=0,1$ or $2$ and $k$ can be any natural number.
And we figure $2^3 \equiv 8 \equiv 1$ so........
$2^{3k+r}= 2^{3k}\times 2^r =(2^3)^k\times 2^r = 8^k \times 2^r \equiv 1^k\times 2^r \equiv 2^r \pmod 7$.  Always.
And from that we can conclude that for all natural numbers we have one of the following $3$ cases:

*

*If $n \equiv 0 \pmod 3$ that is if there is a $k$ so $n = 3k + 0$ then

$2^{n} \equiv 2^0\equiv 1 \pmod 7$.  And our case is always satisfied.


*If $n \equiv 1 \pmod 3$ that is if there is a $k$ so $n = 3k + 1$ then

$2^n \equiv 2^1 \equiv 2 \pmod 7$. And our case is never satisfied (but we we always have $n \equiv 1\pmod 7 \implies 2^n\equiv 2 \pmod 7$.)


*If $n \equiv 2 \pmod 3$ that is if there is a $k$ so $n = 3k + 2$ then

$2^n \equiv 2^2 \equiv 4\pmod 7$. And our case is never satisfied (be we always have $n\equiv 2\pmod 7\implies 2^n\equiv 4\pmod 7$. Always.)
So that's that.
if $n \equiv 0 \pmod 3$ then $2^n \equiv 1\pmod 7$.  Always.  And if $n \not \equiv 0 \pmod 3$ then $2^n \not \equiv 1 \pmod 7$.  Never.
</s>