7
$\begingroup$

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 !

$\endgroup$
  • 2
    $\begingroup$ $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. $\endgroup$ – Jyrki Lahtonen Jul 30 at 12:45
  • 6
    $\begingroup$ 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$. $\endgroup$ – Alexey Burdin Jul 30 at 12:46
  • 3
    $\begingroup$ 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$. $\endgroup$ – peter a g Jul 30 at 13:19
  • 2
    $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Jul 30 at 14:22
  • 3
    $\begingroup$ @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$. $\endgroup$ – Jyrki Lahtonen Jul 30 at 15:03
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes , I was able to solve from here , in fact , I have seen many ways of solving this now , thanks ! $\endgroup$ – ARROW Aug 6 at 11:44
  • $\begingroup$ @ARROW You are welcome :) The more ways you see, the more you can learn. $\endgroup$ – FormulaWriter Aug 6 at 12:02
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.