AMC12 2014 B

AMC12 2014 B · Q23

AMC12 2014 B · Q23. It mainly tests Primes & prime factorization, Remainders & modular arithmetic.

The number 2017 is prime. Let $S = \sum_{k=0}^{62} \binom{2014}{k}$. What is the remainder when $S$ is divided by 2017?

数2017是素数。设$S = \sum_{k=0}^{62} \binom{2014}{k}$。$S$除以2017的余数是多少？

(A) 32 32

(B) 684 684

(D) 1576 1576

(E) 2016 2016

Answer

Correct choice: (C)

正确答案：（C）

Solution

Answer (C): Let $n=\binom{2014}{k}$. Note that $2016\cdot2015\equiv(-1)(-2)=2\pmod{2017}$ and $2016\cdot2015\cdots(2015-k)\equiv(-1)(-2)\cdots(-(k+2))=(-1)^k (k+2)!\pmod{2017}$. Because $n\cdot k!\cdot(2014-k)!=2014!$, it follows that $\,n\cdot k!\cdot(2014-k)!\cdot\big((2015-k)\cdots2015\cdot2016\big)\cdot2 \equiv 2014!\cdot2015\cdot2016\cdot(-1)^k (k+2)!\pmod{2017}.$ Thus $2n\cdot k!\cdot2016!\equiv(-1)^k (k+2)!\cdot2016!\pmod{2017}.$ Dividing by $2016!\cdot k!$, which is relatively prime to $2017$, gives $2n\equiv(-1)^k (k+2)(k+1)\pmod{2017}.$ Thus $n\equiv(-1)^k\binom{k+2}{2}\pmod{2017}$. It follows that $S=\sum_{k=0}^{62}(-1)^k\binom{k+2}{2}=1+\sum_{k=1}^{31}\left(\binom{2k+2}{2}-\binom{2k+1}{2}\right)$ $=1+\sum_{k=1}^{31}(2k+1)=32^2=1024\pmod{2017}.$

答案（C）：令 $n=\binom{2014}{k}$。注意 $2016\cdot2015\equiv(-1)(-2)=2\pmod{2017}$，并且 $2016\cdot2015\cdots(2015-k)\equiv(-1)(-2)\cdots(-(k+2))=(-1)^k (k+2)!\pmod{2017}$。由于 $n\cdot k!\cdot(2014-k)!=2014!$，因此 $\,n\cdot k!\cdot(2014-k)!\cdot\big((2015-k)\cdots2015\cdot2016\big)\cdot2 \equiv 2014!\cdot2015\cdot2016\cdot(-1)^k (k+2)!\pmod{2017}.$ 于是 $2n\cdot k!\cdot2016!\equiv(-1)^k (k+2)!\cdot2016!\pmod{2017}.$ 用与 $2017$ 互素的 $2016!\cdot k!$ 同除，得到 $2n\equiv(-1)^k (k+2)(k+1)\pmod{2017}.$ 因此 $n\equiv(-1)^k\binom{k+2}{2}\pmod{2017}$。从而 $S=\sum_{k=0}^{62}(-1)^k\binom{k+2}{2}=1+\sum_{k=1}^{31}\left(\binom{2k+2}{2}-\binom{2k+1}{2}\right)$ $=1+\sum_{k=1}^{31}(2k+1)=32^2=1024\pmod{2017}.$

Topics