$ $
풀이. $N$이 임의의 수라 하자. 이제 $N$을 적당한 자리수로 끊어 $N$을 몇 개의 수로 분할한다. 이 분할된 수들의 합을 $S$라 하자. 그러면 $N$과 $S$를 $9$로 나누었을 때의 나머지는 서로 같다. 이 사실이 성립함은 합동식을 이용하면 간단하게 증명이 가능하므로 생략하도록 하자.
$ $
예를 들어 $N = 18274610229$을 생각해 보자. 다음으로 $N$을 $18$, $274$, $6$, $102$, $29$로 적당히 분할한다. 이제 이 수들의 합은 $18+274+6+102+29 = 429$인데 $429$를 $9$로 나눈 나머지는 $6$이므로 원래의 수 $N$을 $9$로 나눈 나머지도 $6$임을 알 수 있게 된다.
$ $
이제 이 사실을 원래 문제에 적용해 보면, $M$을 $9$로 나눈 나머지는 아래의 수
\[ 1 + 2 + \cdots + 2016 = \frac{2018(2018+1)}{2} = 2037171 \]
과 같아야 한다. 또한 $2+0+3+7+1+7+1 = 21$이고 $21$을 $9$로 나누눈 나머지는 $3$이므로, 원래의 수 $M$을 $9$로 나눈 나머지 또한 $3$이 된다..