Congruence $n*2^n + 1 \mod 3$

Question

I want to investigate for which $n\geq0$ the expression $n*2^n + 1$ is divisible by $3$. I’ve tried applying Fermat’s little theorem but without any success and believe this is not the correct way to go about it. Any tips or hints would by highly appreciated.

Best regards, David

Answer 1

Observe that if $n$ is even ($n=2k$) then $2^n \equiv (2^2)^k \equiv 1^k \equiv 1 \pmod{3}$ and when $n$ is odd then $2^n \equiv -1 \pmod{3}$.

Let $n$ be even, then \begin{align*} n2^n+ 1 & \equiv n(1)+1 \pmod{3}\\ & \equiv n+1 \pmod{3} \end{align*}

We want this to be $0 \mod 3$, so $n \equiv 2 \pmod{3}$. We have the following conditions on $n$, $$n \equiv 0 \pmod{2} \quad \text{and} \quad n \equiv 2 \pmod{3}.$$

This can be consolidated as $n \equiv 2\pmod{6}$.

Likewise you can deal with the other case.

Answer 2

Hint $\bmod 3\!:\ 2^{\large n+2}\equiv 2^{\large n}\Rightarrow\, f(n\!+\!\color{#c00}6)\equiv f(n)$ so we need to test only $\color{#c00}6$ values $\,n = 0,1\,\ldots,5$

Remark $ $ Such $\color{#c00}{\text{periodicity}}$ holds much more generally, e.g. above is the special case of the Lemma below where $\,f(x,y) = xy+1,\ g(x) = 2^{\large x},\, m,n = 2,3$.

Lemma $ $ If $\,f:\Bbb Z^2\to \Bbb Z,\,\ g:\,\Bbb N\to \Bbb Z\,$ and $f$ is a polynomial with integer coef's then

$\!\bmod n\!:\,\ \forall x\in \Bbb N\!:\ g(x\!+\!m)\equiv g(x)\ \Rightarrow\ \forall x\in \Bbb N\!:\ f(x\!+\!\color{#c00}{mn},\,g(x\!+\!\color{#c00}{mn}))\equiv f(x,g(x)) $

Proof $\, \begin{align} x\!+\!mn&\,\equiv\, x\\ g(x\!+\!mn)&\equiv g(x)\end{align}$ $\Rightarrow \begin{align} &\ f(x\!+\!mn,\,g(x\!+\!mn))\\ \equiv\, &\ f(x,\,g(x)) \end{align}$ by the Polynomial Congruence Rule

where $\,\ g(x\!+\!mn)\equiv g(x)\ $ follows from $\,g(x\!+\!m)\equiv g(x)\,$ by induction on $\,n$.

Beware as above $\,g(x)\,$ may not be a polynomial so it needn't satisfy $\,x\equiv y\,\Rightarrow\,g(x)\equiv g(y)$

Answer 3

Write $a_n=n2^n+1^n$ and write $(x-2)^2(x-1)=0$ as $x^3=5x^2-8x+4$. Then $$ a_{n+3} = 5a_{n+2} -8a_{n+1}+4a_n $$ Then $a_n \bmod 3$ is $$ 1,0,0,1,2,2,\color{red}{1,0,0,1,2,1,2,2},\dots $$ Because of the linear recurrence, the sequence repeats as soon as it repeats three consecutive terms, $1,0,0$ in this case.

Bottom line $a_n \equiv 0 \bmod 3$ iff $n \equiv 1,2 \bmod 6$.