Prove that a)$\sum_{k=1}^{1008}kC_{2017}^{k}\equiv 0$ (mod $2017^2$ ) b)$\sum_{k=1}^{504}\left ( -1 \right )^kC_{2017}^{k}\equiv 3\left ( 2^{2016}-1 \right )$ (mod $2017^2$ )
Problem
Source:
Tags: number theory
ThE-dArK-lOrD
07.01.2017 17:22
a) is easy. b) Note that for all $j=1,2,\dotsc ,2016$ we have $$\frac{1}{2017}\binom{2017}{j}=\frac{2016!}{j!(2017-j)!}\equiv \frac{(-1)^{j-1}}{j}\pmod{2017}.$$From the identity $(1+1)^{2017}-2=\sum_{j=1}^{2016}{\binom{2017}{j}}$ we get that \begin{align*} \frac{2^{2017}-2}{2017}& \equiv \sum_{j=1}^{2016} {\frac{(-1)^{j-1}}{j}} \pmod{2017}\\ & =\sum_{j=1}^{1008}{\frac{1}{2j-1}} -\sum_{j=1}^{1008}{\frac{1}{2j}} =\sum_{j=1009}^{2016}{\frac{1}{j}}. \end{align*}Now recall the identity $$(i+1)^{2017}-i^{2017}-1=(\sqrt{2}\mathrm{cis} (\pi /4))^{2017}-(i+1)=(2^{1008}-1)(i+1)=\sum_{j=1}^{2016}{\binom{2017}{j}i^j}.$$Considering the real parts of both sides gives us \begin{align*} \frac{2^{1008}-1}{2017}& \equiv \sum_{j=1}^{1008}{\frac{(-1)^{2j-1}}{2j}i^{2j}} \pmod{2017} \\ & =\sum_{j=1}^{1008}{\frac{-(-1)^j}{2j}} \\ & =\frac{1}{2}\left( \sum_{j=1}^{504}{\frac{1}{2j-1}}-\sum_{j=1}^{504}{\frac{1}{2j}}\right) =\frac{1}{2}\sum_{j=505}^{1008}{\frac{1}{j}}, \end{align*}which implies $$2\cdot \frac{2^{1008}-1}{2017}\equiv \sum_{j=505}^{1008}{\frac{1}{j}} \pmod{2017}.$$Combining the above results with Wolstenholme's, we get that $$\sum_{j=1}^{2016}{\frac{1}{j}}\equiv 0\pmod{2017} \implies \sum_{j=1}^{504}{\frac{1}{j}}\equiv -\left( 2\cdot \frac{2^{1008}-1}{2017}+\frac{2^{2017}-2}{2017}\right) \equiv -\frac{3(2^{2016}-1)}{2017} \pmod{2017}.$$Finally, we have $$\frac{1}{2017}\sum_{j=1}^{504}{(-1)^j\binom{2017}{j}}\equiv \sum_{j=1}^{504}{(-1)^j\frac{(-1)^{j-1}}{j}}=-\sum_{j=1}^{504}{\frac{1}{j}}\equiv \frac{3(2^{2016}-1)}{2017}\pmod{2017},$$which implies $$\sum_{j=1}^{504}{(-1)^j\binom{2017}{j}} \equiv 3(2^{2016}-1)\pmod{2017^2}.\quad \blacksquare$$
LittleKesha
23.05.2017 20:31
Someone can post the solution for a)? Thanks
khanhnx
21.05.2019 17:44
Here is my solution for part a Solution We have: $\sum_{k = 1}^{1008}kC_{2017}^{k} = 2017 \sum_{k=1}^{1008}C_{2016}^{k - 1} = \dfrac{2017}{2} \left(\sum_{k=0}^{2016}C_{2016}^{k} - C_2016^1008 \right) = \dfrac{2017}{2} (2^{2016} - C_{2016}^{1008})$ We have: $2^{2016} \equiv 1$ $($ mod $2017$ $)$ and: $C_2016^1008 = \dfrac{1009 . 1010 . ... . 2016}{1008!} = \dfrac{(2017 - 1)(2017 - 2). ... .(2017 - 1008)}{1008!} \equiv 1$ $($ mod $2017$ $)$ Then: $2^{2016} - C_{2016}^{1008} \vdots 2017$ or $\sum_{k = 1}^{1008}kC_{2017}^{k} = \dfrac{2017}{2} (2^{2016} - C_{2016}^{1008}) \vdots 2017^2$
AlastorMoody
28.03.2020 14:17
Vietnam NMO 2017 P6 Part (a) wrote:
Prove,
\begin{align*} \sum_{k=1}^{1008} \binom{2017}{k} k \equiv 0 \pmod{2017^2} \end{align*}
Solution: Notice,
\begin{align*} \sum_{k=1}^{1008} \binom{2017}{k} k = \sum_{k=1}^{1008} 2017 \binom{2016}{k-1} =2017 \sum_{m=0}^{1007} \binom{2016}{m}= \frac{2017}{2} \left( 2^{2016} - \frac{2016!}{(1008!)^2} \right) \end{align*}Thus, we want to show
\begin{align*}2^{2015} \equiv \frac{1}{2} \frac{2016!}{(1008!)^2} \pmod{2017} \end{align*}But the above is true, since $(1008!)^2 \equiv 2016 ! \pmod{2017}$ and $2^{2015} \equiv 2^{-1} \pmod{2017}$ $\qquad \blacksquare$
Vietnam NMO 2017 P6 Part (b) wrote:
Prove, \begin{align*} \sum_{k=1}^{504} (-1)^k \binom{2017}{k} \equiv 3 (2^{2016} -1 ) \pmod{2017^2}
\end{align*}
Solution: We begin with a well-known result. For $1 \le k \le p-1 $,
\begin{align*} \binom{p}{k} \equiv \frac{p}{k} (-1)^{k-1} \pmod{p^2} \end{align*}Which follows due to $(k-1)! (p-k)! \equiv (-1)^k \pmod{p}$. This implies
\begin{align*} \binom{p}{k} \equiv \frac{p}{k} (-1)^{k-1} \equiv 4 (-1)^k \frac{p}{4k} (-1)^{4k-1} \equiv 4 (-1)^k \binom{p}{4k} \pmod{p^2} \end{align*}Thus,
\begin{align*} \sum_{k=1}^{504} (-1)^k \binom{2017}{k} &= \sum_{k=1}^{\tfrac{2017-1}{4}} (-1)^k \binom{2017}{k} \\
&\equiv 4 \sum_{k=1}^{\tfrac{2017 -1}{4}} \binom{2017}{4k} \pmod{2017^2} \\
&\equiv 4 \left[ \sum_{k=0}^{\tfrac{2017 -1}{4}} \binom{2017}{4k} \right] -4 \pmod{2017^2} \\
&\equiv 4 \sum_{n=0}^{2017} \left(\binom{2017}{n} \left( \frac{1^n +(-1)^n + (\sqrt{-1})^n +(- \sqrt{-1})^n }{4} \right) \right) -4 \pmod{2017^2} \\
&\equiv 2^{2017} -4 +\left( 1+ \sqrt{-1} \right)^{2017} + \left( 1 - \sqrt{-1} \right)^{2017} \pmod{2017^2} \\
&\equiv 2^{2017} + 2^{1009} -4 \pmod{2017^2} \\ \end{align*}Thus we want to show,
\begin{align*} 2^{2017} + 2^{1009} -4 \equiv 3 (2^{2016} -1) \pmod{2017^2} \end{align*}\begin{align*} \Longleftrightarrow 2^{2016} -2^{1009} +1 \equiv 0 \pmod{2017^2} \end{align*}\begin{align*} \Longleftrightarrow \left( 2^{1008} -1 \right)^2 \equiv 0 \pmod{2017^2} \end{align*}Which holds since, $2017 \mid 2^{1008} -1$. All that remains now is to show $\sqrt{-1}$ $\pmod{2017^2}$ exists which can be shown using Fermat's Theorem on sum of two squares and the fact that inverse of $a$ $\pmod{m}$ exists iff $\gcd(a,m)$ $=$ $1$ $\qquad \blacksquare$