Find the remainder when $\sum_{n=1}^{2015}{n^2\times2^n}$is divided by 23.

Question

Find the remainder when $\sum_{n=1}^{2015}{n^2\times2^n}$is divided by 23.

I am completely stuck at this to even start , here's the samll thing that I have noticed . When $2^{11}$ is divided by 23 , the remainder is $1$ , so $2^{11k+r}$ is equivalent to $2^r$ (mod 23) , for any natural number $k$. Apart from this nothing useful thing came to my mind .

Could someone please help me to find the remainder ?

Thanks !

Answer 1

With $k=1,2,\cdots,23$ one has $n^22^n\equiv(23m+k)^22^{23m+k}\equiv k^22^{m+k}\pmod{23}$ and since $2015=87\cdot23+14$ you have $$\sum_1^{23}n^22^n\equiv\sum_1^{23}k^22^k=A\pmod{23}\\\sum_{24}^{46}n^22^n\equiv\sum_1^{23}k^22^{k+1}=2A\pmod{23}\\..................................\\..................................\\\sum_{86*23+1}^{87*23}n^22^n\equiv\sum_1^{23}k^22^{86+k}=2^{86}A\pmod{23}$$ Then$$\sum_1^{2001}n^22^2\equiv(1+2+2^3+\cdots+2^{86})A=(2^{87}-1)A\pmod{23}$$ The actual calculation of this is not difficult modulo $23$ and so over the last $14$ terms in play.Naturally you can apply the little known formula given by Alexey Burdin above but here it is about making efforts not to apply that formula.

►I want to verify this way the answer given by the formula above which is $5$.

We have $$A\equiv6\pmod{23}\\2^{87}-1\equiv{11}\pmod{23}\\(2^{87}-1)A\equiv{20}\pmod{23}$$ The remaining $14$ terms partially add up the following module $23$ residus: $$18+1+14+21=8\pmod{23}$$ therefore $$20+8=28\equiv\color{red}5\pmod{23}$$

Indeed, the answers coincide.

Answer 2

So what you said and the fact that $n^2 \equiv(n \mod 23)^2 \pmod{23}$ and $12 \equiv -11 \pmod{23}$ and $13 \equiv -10 \pmod {23}$ and so on makes a periodic sum: (let the sum be $S$) $$S \equiv 1^2\cdot2^1+\dots+11^2\cdot2^{11}$$ $$+(-11)^2\cdot2^{1}+(-10)^2\cdot2^2+\dots+(-1)^2\cdot2^{11}+0+\dots$$ and of course the square makes the negative go out. So we need to find out that $2015=23\cdot87+14$ which makes $$S \equiv 87(1^2\cdot2^1+\dots+11^2\cdot2^{11}+11^2\cdot2^{1}+10^2\cdot2^2+\dots+1^2\cdot2^{11}+0)$$ $$+1^2\cdot2^1+\dots+11^2\cdot2^{11}+11^2\cdot2^{1}+10^2\cdot2^2+9^2\cdot2^3 \tag{since $14\equiv -9 \pmod{23}$}$$ and that makes the rest easy to compute.

Answer 3

Since $2^{11}\equiv 1 \pmod{23}$ then the following holds for integers $q,r\geq 0$:

$$(q23+r)^2 \cdot 2^{q23+r} \equiv r^2 \cdot 2^{q+r} \pmod{23}$$ Therefore: $$ \sum_{r=0}^{22} (q23+r)^2 \cdot 2^{q23+r} \equiv 2^q \sum_{r=0}^{22} r^2 \cdot 2^{r} \pmod{23}$$ $$ \sum_{q=0}^{87} \sum_{r=0}^{22} (q23+r)^2 \cdot 2^{q23+r} \equiv (\sum_{q=0}^{87} 2^q) \sum_{r=0}^{22} r^2 \cdot 2^{r} \pmod{23}$$ Since $\sum_{q=0}^{87} 2^q \equiv 0 \pmod{23}$ (why?) we get $\sum_{n=0}^{88 \cdot 23 -1} n^2 2^n \equiv 0 \pmod{23}$. Does it help? ($88 \cdot 23 -1= 2023$ is not so far from $2015$ ... )