중국인의 나머지 정리

Chinese Remainder Theorem

1. 개요

---

중국의 5세기 문헌인 『손자산경(孫子算經)』[1][2]에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? [3]

이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 '''중국인의 나머지 정리'''가 되었다고 한다. 위 문제는 뭔가 초등학교 문제집에나 나올 법한 느낌이지만[4] 실은 '''연립 합동식''' 문제로, 정수론과 관련된 내용이다. 초등학생들이 못 푸는 게 당연한 것. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다.
아래 정리를 읽기 전에, 정신이 안드로메다로 가는 듯한 느낌(...)을 받지 않기 위해선 반드시 합동식 문서를 읽고 오자. mod에 대해 간단히 설명하자면, $A\left(\text{mod}\,B\right)$면 $B$로 나누어 $A$의 나머지를 생기게 하는 수라는 뜻이다. $C=A\left(\text{mod}\,B\right)$라면 일반적인 방정식으로는 $C=Bk+A$, ($0\leq A<B, k\in$ℤ)로 나타난다.
자세한 정리는 다음과 같다.

$m_1,m_2,\cdots,m_n$이 쌍마다 서로 소(즉, $\gcd\left(m_i,m_j\right)=1,i\neq j$)이면, 다음 연립 합동식

$x\equiv a_1\left(\text{mod}\,m_1\right)$

$x\equiv a_2\left(\text{mod}\,m_2\right)$

$x\equiv a_3\left(\text{mod}\,m_3\right)$

$\vdots$

$x\equiv a_n\left(\text{mod}\,m_n\right)$

은 법 $m_1 m_2\cdots m_n$에 대하여 유일한 해를 갖는다.

2. 증명

---

증명은 크게 존재성, 유일성 두 가지로 나뉜다. 또한 이 정리를 증명하기에 앞서 도움정리를 알아두어야 한다.

2.1. 도움정리 1

---

양의 정수 $m$과 $a_1,a_2,\cdots,a_n$에 대하여 $m$이 $a_1,a_2,\cdots,a_n$와 각각 서로소이면, $m$과 $a_1a_2\cdots a_n$은 서로소이다.

증명

서로소가 아니라고 가정하자. 그럼 $m$과 $a_1a_2\cdots a_n$의 공약수인 소수 $p$가 존재한다. $p\mid a_1a_2\cdots a_n$이므로 $p\mid a_i$인 $a_i$가 존재한다. 그러면 $p$는 $a_i$와 $m$을 모두 나누고, 이는 가정에 모순이다.

2.2. 도움정리 2

---

양의 정수 $m$과 $a_1,a_2,\cdots,a_n$에 대하여 $m$이 $a_1,a_2,\cdots,a_n$의 각각의 배수이면 $m$은 $\text{lcm}\left(a_1,a_2,\cdots,a_n\right)$의 배수이다.

증명

나눗셈 정리에 의하여 $m=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r$ 을 만족하는 정수 $q,r$이 유일하게 존재한다 ($0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right)$). 그런데 $a_i$가 $m$과 $\text{lcm}\left(a_1,a_2,\cdots,a_n\right)$을 모두 나누므로 $a_i$는 $r$도 나눠야 한다. 이것은 모든 $i$에 대해 참이므로 $r$은 $\text{lcm}\left(a_1,a_2,\cdots,a_n\right)$보다 작은 $a_i$들의 공배수이다. 이걸 만족하는 값은 $r=0$밖에 없으며, 이는 곧 $m$이 $\text{lcm}\left(a_1,a_2,\cdots,a_n\right)$의 배수임을 보인다.

2.3. 도움정리 3

---

양의 정수 $a_1,a_2,\cdots,a_n$에 대하여 $\gcd\left(a_i,a_j\right)=1,i\neq j$(즉, '''쌍마다 서로 소'''(pairwise relatively prime))이면,

$\text{lcm}\left(a_1,a_2,\cdots,a_n\right)=a_1 a_2 \cdots a_n$이 성립한다.

이에 대한 증명은 최소공배수 참조. 사실 증명이라 할 것도 없다.

2.4. 존재성

---

$m=m_1 m_2 \cdots m_n$라고 하자. 또, $n_k=\frac{m}{m_k}$라고 놓자. 즉, $n_k$는 $m_k$를 제외한 나머지 $m_i$들의 곱을 의미한다.
도움정리 1로부터 $\gcd\left(n_k,m_k\right)=1$이다. 그럼 베주 항등식에 의해,
$s_k n_k + t_k m_k =1$
을 만족하는 정수 $s_k,t_k$가 존재한다. 이를 합동식 형태로 고치면,
$s_k n_k\equiv1\left(\text{mod}\,m_k\right)$
이다. 이제
$x = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n$
라고 놓자. $j\neq k$이면 $m_k\mid n_j$이고,[5] 따라서
$x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\text{mod}\,m_k\right)$이다.(1<=k<=n인 임의의 자연수)[6][7]
즉, $x$는 주어진 연립 합동식의 한 해이다.

2.5. 유일성

---

$x,y$가 주어진 연립 합동식의 해라고 하자.[8]그러면,
$x\equiv a_1\left(\text{mod}\,m_1\right)$, $y\equiv a_1\left(\text{mod}\,m_1\right)$
$x\equiv a_2\left(\text{mod}\,m_2\right)$, $y\equiv a_2\left(\text{mod}\,m_2\right)$
$\vdots$
$x\equiv a_n\left(\text{mod}\,m_n\right)$, $y\equiv a_n\left(\text{mod}\,m_n\right)$
이다. 그러므로, 임의의 $k\,\left(1\leq k\leq n\right)$에 대하여, $x\equiv a_k\equiv y\left(\text{mod}\,m_k\right)$이고, 그래서 $x-y\equiv0\left(\text{mod}\,m_k\right)$이다.[9] 즉, $x-y$는 모든 $m_k$들의 배수이다. 따라서 도움정리 2에 의해,
$\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)$
이다. 그런데, $m_1,m_2,\cdots,m_n$들이 쌍마다 서로 소이므로, 도움정리 3으로부터
$m_1 m_2 \cdots m_n\mid\left(x-y\right)$이다. 즉,
$x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right)$이고, 이는 주어진 연립 합동식의 해가 유일함을 보인다.

3. 문제를 푸는 방법

---

위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다.
3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 $3\times5\times7=105$에 대하여 유일한 해를 가진다. $m=105,n_1=35,n_2=21,n_3=15$라 하자.
$n_1 s_1\equiv35s_1\equiv2s_1\equiv1\left(\text{mod}\,3\right)$
$n_2 s_2\equiv21s_2\equiv s_2\equiv1\left(\text{mod}\,5\right)$
$n_3s_3\equiv15s_3\equiv s_3\equiv1\left(\text{mod}\,7\right)$
을 풀면 $s_1=2,s_2=1,s_3=1$가 해임을 알 수 있다.[10] 그러므로 $x \equiv a_1 n_1 s_1 + a_2 n_2 s_2 + a_3n_3s_3 \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \equiv 233 \equiv 23 \left(\text{mod}\,105\right)$이다.
따라서 $x\equiv23\left(\text{mod}\,105\right)$가 주어진 연립 합동식의 해이다.

4. 결론

---

풀어서 말하면 서로소인 $n$개의 수 각각에 대해 일정한 나머지를 만족하는 수는 그들 $n$개의 최소공배수에 일정한 나머지를 더한 값으로 나타난다는 정리이다. 사실 어떤 자연수 $A$에 대해 일정한 나머지 $B$를 가지는 수에 $A$의 배수를 더하면 이 또한 $A$로 나눈 나머지가 $B$이므로, 존재성과 유일성을 증명하고 나면 $n$개 수의 최소공배수마다 조건을 만족하는 수가 반복되어 나타난다는 것은 쉽게 유추가 가능하다.

5. 관련 문서

---

• 합동식
• 최대공약수
• 최소공배수
• 환(대수학)#s-6.1

[1] 여기에서의 '손자(孫子)'는 『손자병법』을 쓴 그 '손자'와 한자는 같지만 그보다 훨씬 후대의 인물이다.

[2] 중국의 옛 수학서에는 이 『손자산경(孫子算經)』 외에도, 『주비산경(周髀算經)』, 『구장산술(九章算術)』, 『해도산경(海島算經)』, 『오조산경(五曹算經)』, 『하후양산경(夏侯陽算經)』, 『장구건산경(張邱建算經)』, 『오경산술(五經算術)』, 『집고산경(緝古算經)』, 『철술(綴術)』 등이 있다. 이들을 통틀어 '산경십서(算經十書)'로 칭한다.

[3] 풀이는 아래쪽 문단 참조. 답은 23, 128 등등이다.

[4] 그런데 그것이 실제로 일어났습니다 의외로 초등학교 문제집에 이런 문제들이 나오고, 심지어 중학교 방정식 단원에 나오는 경우도 있다.

[5] $n_k$의 정의 때문에 성립

[6] 나머지 $a_j n_j s_j$는 $m_k$로 나누면 나머지가 0 이므로 $j=k$인 경우만 생각해 주면 된다.

[7] 또한 $n_k s_k$는 위 $s_k n_k\equiv 1\left(\text{mod}\,m_k\right)$와 합동식의 성질 때문에 1로 바뀐다.

[8] 임의의 두 답이 같음을 보이는 방법은 유일성을 증명하는 데 자주 쓰이는 테크닉이다.

[9] 추이율. 합동식의 성질 참조

[10] 여러 값 중 아무거나 고르면 된다.