중국인의 나머지 정리
Chinese Remainder Theorem
1. 개요
중국의 5세기 문헌인 『손자산경(孫子算經)』[1][2]에는 다음과 같은 문제가 있다고 한다.
이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 '''중국인의 나머지 정리'''가 되었다고 한다. 위 문제는 뭔가 초등학교 문제집에나 나올 법한 느낌이지만[4] 실은 '''연립 합동식''' 문제로, 정수론과 관련된 내용이다. 초등학생들이 못 푸는 게 당연한 것. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다.3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? [3]
아래 정리를 읽기 전에, 정신이 안드로메다로 가는 듯한 느낌(...)을 받지 않기 위해선 반드시 합동식 문서를 읽고 오자. 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$$은 서로소이다.
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)$$의 배수이다.
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. 관련 문서
[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] 여러 값 중 아무거나 고르면 된다.