중국인의 나머지 정리

• 상위 항목: 수학 관련 정보, 정수론

Chinese Remainder Theorem.

1 개요

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

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

이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다. 위 문제는 뭔가 초등학교 문제집에나 나올 법한 문체지만 실은 연립 합동식이다. 초등학생들이 못 푸는게 당연한 것. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다.

아래 정리를 읽기전에, 멘탈이 나가기 싫다면 반드시 합동식 문서를 읽고 오자.사실 수학과 입장에선 별로 어렵지도 않다. mod에 대해 간단히 설명하자면, [math]A\left(\text{mod}\,B\right)[/math]면 [math]B[/math]로 나누어 [math]A[/math]의 나머지를 생기게 하는 수라는 뜻이다. [math]C=A\left(\text{mod}\,B\right)[/math]라면 일반적인 방정식으로는 [math]C=Bk+A[/math], ([math]0\leq A\ltB, k\in[/math]ℤ)로 나타난다.

자세한 정리는 다음과 같다.

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

[math]x\equiv a_1\left(\text{mod}\,m_1\right)[/math]
[math]x\equiv a_2\left(\text{mod}\,m_2\right)[/math]
[math]x\equiv a_3\left(\text{mod}\,m_3\right)[/math]
[math]\vdots[/math]
[math]x\equiv a_n\left(\text{mod}\,m_n\right)[/math]
은 법 [math]m_1 m_2\cdots m_n[/math]에 대하여 유일한 해를 갖는다.

2 초등적 증명

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

2.1 도움정리 1

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

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

2.2 도움정리 2

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

증명

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

2.3 도움정리 3

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

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

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

2.4 존재성

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

2.5 유일성

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

3 대수적 증명

[math]m_1, m_2, \cdots, m_n[/math]은 쌍마다 서로소이므로 유한생성아벨군의 기본정리에 의해 [math]\mathbb{Z_{m_1m_2\cdots m_n}}[/math]은 [math]\mathbb{Z_{m_1}} \times \mathbb{Z_{m_2}} \times \mathbb{\cdots} \times \mathbb{Z_{m_n}}[/math]과 isomorphic하다. 따라서 [math]\mathbb{Z_{m_1m_2\cdots m_n}}[/math]에서의 해는 [math]\mathbb{Z_{m_1}} \times \mathbb{Z_{m_2}} \times \mathbb{\cdots} \times \mathbb{Z_{m_n}}[/math]에서의 해와 유일하게 대응된다.

4 문제를 푸는 방법

위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다.

3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 [math]3\times5\times7=105[/math]에 대하여 유일한 해를 가진다. [math]m=105,n_1=35,n_2=21,n_3=15[/math]라 하자.
[math]n_1 s_1\equiv35s_1\equiv2s_1\equiv1\left(\text{mod}\,3\right)[/math]
[math]n_2 s_2\equiv21s_2\equiv s_2\equiv1\left(\text{mod}\,5\right)[/math]
[math]n_3s_3\equiv15s_3\equiv s_3\equiv1\left(\text{mod}\,7\right)[/math]
을 풀면 [math]s_1=2,s_2=1,s_3=1[/math]가 해임을 알 수 있다. 그러므로 [math]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)[/math]이다.
따라서 [math]x\equiv23\left(\text{mod}\,105\right)[/math]가 주어진 연립 합동식의 해이다.

5 결론

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

6 관련 항목

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