Problems and Solutions #013

Problem #013

$1$부터 $2016$까지의 모든 수를 일렬로 나열한 수 $M$을 생각하자. 즉,

$$M=123\dots 891011\dots 20152016.$$

이때, $M$을 $9$로 나누었을 때의 나머지를 구하여라.

$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{2016(2016+1)}{2}=2033136$$

과 같아야 한다. 또한 $2+3+3+1+3+6=18$이고 $18$은 $9$로 나누어 떨어지므로, 원래의 수 $M$ 또한 $9$로 나누어 떨어짐을 알 수 있다. 따라서 나머지는 $0$.