Find all n such that : $3 \mid (n2^{n}+1)$

Question

Question :

Determine all natural numbers n such that 3

divides $n\cdot2^{n}+1$

Actually I don't have any ideas to approach but

my efforts :

I see $n=1,2,7,8,13,14$ so I think :

$n=6k+1$ and $n=6k+2$ $k\in \Bbb{N} $

If I'm not wrong but I don't know how ? I prove it ?

Answer 1

$$2 \equiv -1 \pmod{3} \Rightarrow 2^n \equiv (-1)^n \pmod{3} \Rightarrow \\ n2^n+1 \equiv n(-1)^n+1 \pmod{3}$$ Now $3 \mid n2^n+1 \iff 3\mid n(-1)^n+1$, so we will go case by case:

• $n=6k \Rightarrow n(-1)^n+1=6k+1$ has no solutions
• $n=6k+1 \Rightarrow n(-1)^n+1=-6k$ - all are solutions
• $n=6k+2 \Rightarrow n(-1)^n+1=6k+3$ - all are solutions
• $n=6k+3 \Rightarrow n(-1)^n+1=-6k-2$ has no solutions
• $n=6k+4 \Rightarrow n(-1)^n+1=6k+5$ has no solutions
• $n=6k+5 \Rightarrow n(-1)^n+1=-6k-4$ has no solutions

---

Obvious question is why looking at $n=6k+r$? Well:

• $n=2k+r$ is good for dealing with $(-1)^n$, but doesn't help at all with $3 \mid ...$ part
• $n=3k+r$ helps with $3 \mid ...$, but doesn't say a lot about $(-1)^n$.

Combining both seems a better strategy.

Answer 2

Your hypothesis seems very compelling! All you need to do is to show that $$(n+6)2^{n+6}=64(n+6)2^n\equiv n 2^n\pmod3$$ for all natural $n$. Then your observation that it works for only 1 and 2 out of the first six natural numbers is all you need.

Answer 3

Use $\mod 6$ so that $$n2^{n}+1 \equiv0 \mod6$$ or $$n2^{n}+1 \equiv3 \mod6$$ For the first congruency... $$n2^n\equiv5\mod6$$ Trying for diffrent $n \mod6$ you find that $n\not\equiv\mod6$

For the second... $$n2^n\equiv2\mod6$$ Which has solutions at $n\equiv1,2\mod6$

Answer 4

$2^n \equiv (-1)^n \pmod 3$.

So if $n$ is even then $n2^n + 1\equiv n+1 \equiv 0 \pmod 3$ and $n\equiv -1\pmod 3$.

And so $n\equiv 0 \pmod 2$ and $n\equiv 2\pmod 3$ so $n\equiv 2\pmod 6$.

And indeed $(6k+2)2^{6k+2}+1=(6k+2)4^{3k+1}+1\equiv (6k+2)*1^{3k+1} +1\equiv 6k + 2+ 1\equiv 0 \pmod 3$.

If $n$ is odd then $n2^n+1 \equiv -n+1\equiv 0 \pmod 3$ so $n\equiv 1\pmod 3$.

And so $n\equiv 1 \pmod 2$ and $n\equiv 1 \pmod 3$ so $n\equiv 1 \pmod 6$.

And indeed $(6k+1)2^{6k+1}+1\equiv 2^{6k+1}+1\equiv 4^{3k}*2 + 1\equiv 1^{3k}*2 + 1 \equiv 2+ 1\equiv 0\pmod 3$.

...

To check that $n\equiv 0,3,4,5\pmod 6$ can not be solutions, clearly $n\equiv 0,3\pmod 6$ imply $3|n$ so $3\not \mid n2^{n} + 1$.

And $(6k + 3 + i)2^{6k+3 + i}+1\equiv i2^{6k+ 3+i}+1\equiv i4^k*2^{3+i}+1\equiv i2^32^i\equiv i8*2^i +1\equiv -i2^i+1\pmod 3$ and $-2^1+1 \equiv -1\pmod 3$ and $-2*2^2+1\equiv -7\equiv -1\pmod 3$.