lean_workbook_plus_62554

Let $d_n$ be the remainder when $c_n$ is divided by 2010. The desired statement is equivalent to proving that there exist distinct indices $i$ and $j$ such that $d_i = d_j$ . Assume that this is not true; therefore all $d_k$ are distinct. As a result, $d_k$ takes on the values $0$ to $2009$ exactly once for each $k$ . The sum of all $d_k$ is $\frac{2009 \cdot 2010}{2} \equiv 2009 \cdot 1005 \equiv 1005 \pmod{2010}$ . However, the sum of all $c_k$ is $\frac{4020 \cdot 4021}{2} \equiv 2010 \cdot 4021 \equiv 0 \pmod{2010}$ . Now, for all $k$ , $c_k - d_k = 2010l$ for some integer $l$ , so we must have that $\sum c_k \equiv \sum d_k \pmod{2010}$ , but we have just shown that this is not true. Therefore, the original assumption is not true, so using proof by contradiction, we have the desired result.