중국인의 나머지 정리

중국인의 나머지 정리에 대해서 찾아보면 수학적인 용어, 기호들을 남발하면서 설명을 하여 그 내용을 이해하기 어려운 경우가 대부분이다. 여기서는 간단한 예제로부터 중국인의 나머지 정리를 설명함으로써 수학에 자신 없는 분들의 이해를 돕고자 한다.
다음의 예는 중국의 5세기 문헌인 손자산경에 나오는 문제를 오늘날 대한민국의 학교 시험에 나올만한 문제로 각색한 것이다.

어떤 사람의 나이를 3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는다고 한다. 이 조건을 만족하는 사람 중 가장 어린 사람의 나이를 구하시오.

3으로 남으면 2가 남는 조건

$5$와 $7$의 공배수이면서 $3$으로 나누면 $2$가 남는 수 중 최소의 수를 찾아보자.
$5$와 $7$의 최소공배수가 $35$이므로 $5$ 와 $7$의 공배수는 $35a$ 로 나타낼 수 있다. 이때, $35a=33a+2a$ 으로 나타낼 수 있고, $33a$ 는 $3$ 의 배수이므로 $2a$ 가 $3$으로 나누어 $2$ 남는 수이면 된다. 따라서 $a=1$ 일 때가 최소이고, 우리가 찾는 수는 $35$ 가 된다.

5로 나누면 3이 남는 조건

$3$과 $7$의 공배수이면서 $5$로 나누면 $3$이 남는 수 중 최소의 수를 찾아보자.
$3$ 과 $7$ 의 최소공배수가 $21$ 이므로 $3$ 과 $7$ 의 공배수는 $21b$ 로 나타낼 수 있다. 이때, $21b=20b+b$ 로 나타낼 수 있고, $20b$ 는 $5$의 배수이므로 $b$ 가 $5$로 나누어 $3$ 남는 수이면 된다. 따라서 $b=3$ 일 때가 최소이고, 우리가 찾는 수는 $63$ 이 된다.

7로 나누면 2가 남는 조건

$3$과 $5$의 공배수이면서 $7$로 나누면 $2$ 가 남는 수 중 최소의 수를 찾아보자.
$3$ 과 $5$ 의 최소공배수가 $15$ 이므로 $3$ 과 $5$ 의 공배수는 $15c$ 로 나타낼 수 있다. 이때, $15c=14c+c$ 로 나타낼 수 있고, $14c$ 는 $7$의 배수이므로 $c$ 가 $7$로 나누어 $2$ 남는 수이면 된다. 따라서 $c=2$ 일 때가 최소이고, 우리가 찾는 수는 $30$ 이 된다.

합치자

위에서 구한 세 개의 수를 모두 더해보면 $35+63+30=128$ 이 된다. 이 수는 문제의 조건을 모두 만족시키는 수이다.
먼저 $128$ 을 $3$ 으로 나눈 나머지는 ($63$ 과 $30$ 은 $3$의 배수이므로) $35$ 를 $3$ 으로 나눈 나머지와 같다.
마찬가지로 $128$ 을 $5$ 로 나눈 나머지는($35$ 와 $30$ 이 $5$ 의 배수이므로) $63$ 을 $5$ 로 나눈 나머지와 같다.
마지막으로 $128$ 을 $7$ 로 나눈 나머지는 ($35$ 와 $63$ 이 $7$ 의 배수이므로) $30$ 을 $7$ 로 나눈 나머지와 같다.

마지막 단계

위의 내용만을 본다면 우리가 찾는 가장 젊은 사람의 나이는 $128$ 살이라고 생각할 수 있겠지만, 저 정도면 기네스북에 오를만한 나이 아닌가? 따라서 우리는 $128$ 을 다시 분해하여 생각해 봐야 한다.
$3, 5, 7$의 최소공배수가 $105$ 이므로 $128=105+23$ 으로 분해할 수 있다. 여기서 $105$ 는 $3, 5, 7$ 로 모두 나누어 떨어지므로, 나머지를 결정하는 수는 $23$ 이다. 따라서 애초에 $128$ 이 문제의 조건을 모두 만족시켰다면 $23$ 도 문제의 조건을 모두 만족시킬 것이다. 즉, 우리가 찾는 가장 젊은 사람의 나이는 $23$ 살이 되는 것이다.
일반적으로 생각한다면 $105$로 나누어 $23$ 이 남는 수들은 문제의 조건을 모두 만족시키기 때문에 $105x+23$ (단, $x$ 는 정수) 꼴이 문제의 조건을 만족하는 수가 될 수 있다.