For which $n \ge 0$ is $n \cdot 2^n + 1$ divisible by 3? $\textbf{Edit:}$
Thank you all so much for all your help! Superglad I chose to ask. All your different approaches were very insightful and taught me a lot. Thank you!
Same question: Found here.
Hi,
I'm a bit stuck with my question. I've read through the answers in the above link, but I cannot quite understand the answers fully. I don't want to hijack the other thread either, so I thought I'd start a separate thread.
$\textbf{The question is:}$
For which ${n \ge 0}$ is the number ${n \cdot 2^n + 1}$ divisible by 3?
I'v gotten this far in my understanding:
For even ${n(n=2k)}$:
\begin{equation}
      \begin{aligned}
          2^n&=2^{2k} \equiv_3 4^k \equiv_3 1^k \equiv_3 1\\
          n\cdot 2^n+1 &\equiv_3 n\cdot 1 + 1 \equiv_3 n +1
      \end{aligned}
 \end{equation}
For odd ${n(n=2k+1)}$:
\begin{equation}
       \begin{aligned}
           2^{2k+1}&=2^{2k}\cdot 2 \equiv_3 1^k \cdot -1 \equiv_3 1 \cdot - 1 \equiv_3 -1\\
           n\cdot 2^n+1 &\equiv_3 n\cdot -1 + 1 \equiv_3 -n +1
       \end{aligned}
  \end{equation}
One of the answers in the link above mentioned
\begin{equation}
n\equiv 0 (\text{mod 2})\qquad n\equiv 2(\text{mod 3})
\end{equation}
which could be "consolidated as ${n\equiv 2 (\text{mod 6})}$".
I don't understand what the "consolidate"-part means.
So, would someone please like to share some knowledge and insights with me? It feels like I'm almost there, but still a far way to go.
Thanks
 A: Respecting the comments from the OP, all the steps used in the answer have been rigorously expanded.

Of course, $n≠3k,~ k\in\mathbb Z^{+}$.
Take $n=3k-1,~k\in\mathbb Z^{+}$, then you have
$$\begin{align}&\frac{(3k-1)\times 2^{3k-1}+1}{3}\in\mathbb Z^{+}\\
\implies &\frac{2^{3k-1}-1}{3}\in\mathbb Z^{+} \\
\implies &3k-1=2m,~m\in\mathbb Z^{+}\\
\implies &\begin{cases}n=3k-1\\ 3k-1=2m\end {cases}\\
\implies &k=2k'-1,~k'\in\mathbb Z^{+}\\
\implies &n=3(2k'-1)-1,~k'\in\mathbb Z^{+}\\
\implies &n=6k'-4,~k'\in\mathbb Z^{+}\\
\implies &n=6k-4,~k'\longmapsto k .\end{align}$$
Finally take $n=3k-2,~k\in\mathbb Z^{+}$, you have
$$\begin{align}&\frac{(3k-2)\times 2^{3k-2}+1}{3}\in\mathbb Z^{+}\\
\implies &\frac{2^{3k-1}-1}{3}\in\mathbb Z^{+} \\
\implies &3k-1=2m,~m\in\mathbb Z^{+}\\
\implies &\begin{cases}n=3k-2\\ 3k-1=2m\end {cases}\\
\implies &k=2k'-1,~k'\in\mathbb Z^{+}\\
\implies &n=3(2k'-1)-2,~k'\in\mathbb Z^{+}\\
\implies &n=6k'-5,~k'\in\mathbb Z^{+}\\
\implies &n=6k-5,~k'\longmapsto k .\end{align}$$

Thus, our exact answer is:
$$\color {gold}{\boxed {\color{black} {n=6k-4,~n=6k-5,~k\in\mathbb Z^{+}.}}}
$$

Explanations:

*

*If $n=3k$, then

$$\frac{3k\times 2^{3k}+1}{3}=k\times 2^{3k}+\frac 13\not\in\mathbb Z^{+}.$$

*

*If $\frac{2^{3k-1}-1}{3}\in\mathbb Z^{+}$, then $3k-1=2m,~m\in\mathbb Z^{+}$. Because,

$$\frac{2^{2m}-1}{3}=\frac{4^m-1^m}{3}=\frac{(4-1)(4^{m-1}+4^{m-2}+\cdots+1)}{3}\in\mathbb Z^{+}, ~\forall m\in\mathbb Z^{+}.$$
A: Note that $2^n\equiv (-1)^n\pmod 3$ for all $n$, so $2^n\equiv 1$ if $n$ is even and $2^n\equiv 2$ otherwise. Now you have just $6$ cases: $n\pmod 3$ determines $n$, and $n\pmod 2$ determines $2^n$.
Just check what happens when $n=0,1,2,3,4,5$.
A: $$n\equiv 0 \text{ (mod 2)} \;\text{ and }\;n\equiv 2\text{ (mod 3)}\\\iff n-2\equiv 0 \text{ (mod 2)} \;\text{ and }\;n-2\equiv 0\text{ (mod 3)}\\\iff n-2 \;\text{ is a multiple of both 2 and 3}\\\iff n-2 \;\text{ is a multiple of  lcm(2,3)}\\\iff n\equiv 2 \text{ (mod 6)}$$

Continuing where you left off:

*

*For even ${n(n=2k)}$: $$ 2^n=2^{2k} \equiv_3 4^k \equiv_3 1^k
   \equiv_3 1.\\ n\cdot 2^n+1 \equiv_3 n\cdot 1 + 1 \equiv_3 n
   +1\equiv_3 n -2.\\ n \cdot 2^n + 1 \text{ is divisible by 3} \iff n \equiv_3 2 \text { and } n\equiv_2 0\\\iff n\equiv_6 2. $$

*For odd ${n(n=2k+1)}$: $$ 2^{2k+1}=2^{2k}\cdot 2 \equiv_3 1^k \cdot
   -1 \equiv_3 1 \cdot - 1 \equiv_3 -1.\\ n\cdot 2^n+1 \equiv_3 n\cdot -1 + 1 \equiv_3 -n +1.\\ n \cdot 2^n + 1 \text{ is divisible by 3} \iff n \equiv_3 1 \text { and } n\equiv_2 1\\\iff n\equiv_6 1. $$
Hence, for $n\geq0,$ $$n \cdot 2^n + 1 \text{ is divisible by 3} \\\iff n=\equiv_6 1 \text{ or } 2 \\\iff n\in \{6k+1\mid k\in\mathbb{Z}_0^+\} \cup\{n=6k+2\mid k\in\mathbb{Z}_0^+\}. $$
A: HINT:
$n\pmod3$ is determined by $n\pmod3$, and $2^n\pmod3$ is determined by $n\pmod2$, so $n2^n+1\pmod3$ is determined by $n\pmod6$. Now, all that is left is to check the values for $n=0,1,2,3,4,5$.
