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

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 .

Thanks !

• $n^2$ repeats periodically modulo $23$ with period $23$, so by the Chinese remainder theorem $n^2\cdot2^n$ repeats with period $23\cdot11$. That opens up a possibility... Observe that both factors cycle their values independently from each other. – Jyrki Lahtonen Jul 30 at 12:45
• I'd rather find the explicit sum. $\sum\limits_{k=1}^n k^2\cdot 2^k=2(2^n\cdot n^2-2^{n+1}\cdot n+3\cdot 2^n-3)$. The answer is $5$. – Alexey Burdin Jul 30 at 12:46
• Just to explain one way to get @AlexeyBurdin's explicit sum: use $$\sum_{k=1}^nx^k ={x^{n+1}-x\over x -1},$$ apply $x {d\over dx}$ twice, and set $x=2$. – peter a g Jul 30 at 13:19
• @AlexeyBurdin What I was trying to get at it with my "hint" is that as a consequence of the two periods being coprime (so CRT applies) $$\sum_{k=1}^{23\cdot11}k^2\cdot2^k\equiv\left(\sum_{j=0}^{22} j^2\right)\left(\sum_{i=0}^{10}2^i\right)\pmod{23}.$$ Each $k$ matches with a unique pair $(i,j)$ and vice versa. – Jyrki Lahtonen Jul 30 at 14:22
• @AlexeyBurdin $$\sum_{j=0}^nj^2=\frac16 n(n+1)(2n+1),$$ $$\sum_{i=0}^k2^i=2^{k+1}-1.$$ I'm sure the participants of the contest this is from were expected to know those :-) Actually, given that $2$ has order $11$ modulo $23$, its powers are exactly the non-zero quadratic residues, so those two sums are trivially congruent to each other modulo $23$. – Jyrki Lahtonen Jul 30 at 15:03

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}$$

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$$ ... )
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.