중국인의 나머지 정리

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)란, 정수론과 추상대수학에 관한 정리이다. 정수론에서는 연립합동식의 해를 구하는 방법이라 생각하면 된다. 정수론 내용이 다 그렇듯이 대학교에 가서나 배우게 되지만, 수학 경시대회를 준비한다면 알아놔야 한다. 정확히 말하면 연립합동식을 푸는 방법만 알면 되지만...

이름이 왜 하필 중국인의 나머지 정리냐 하면, 5세기의 중국 수학서 손자산경에 연립합동식 문제가 처음 등장했기 때문. 그 문제는 다음과 같다.

“	개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?	“
— 《孫子算經》 하권(下卷) 문제 26번

위 문제는 [math]\displaystyle{ \begin{cases} x\equiv2\pmod3\\x\equiv3\pmod5\\x\equiv2\pmod7\end{cases} }[/math]와 동치이다. 자세한 풀이는 아래쪽 문단의 예시를 참조.

정수론에서

정수론에서의 중국인의 나머지 정리는 다음과 같다.

[math]\displaystyle{ m_1,m_2,\cdots,m_n }[/math]이 쌍마다 서로소이면, 다음 연립 합동식 [math]\displaystyle{ \begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\quad\vdots\\x\equiv a_n\pmod{m_n}\end{cases} }[/math]은 법 [math]\displaystyle{ m_1m_2\cdots m_n }[/math]에 대하여 유일한 해를 갖는다.

증명은 크게 존재성과 유일성으로 나뉘며, 본 증명 전에 도움정리를 먼저 증명한다.

도움정리 1

양의 정수 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]에 대해, [math]\displaystyle{ m }[/math]이 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]와 각각 서로소면, [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ a_1a_2\cdots a_n }[/math]도 서로소이다.

증명

서로소가 아니라고 가정하자. 그럼 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ a_1a_2\cdots a_n }[/math]의 소수인 공약수 [math]\displaystyle{ p }[/math]가 존재한다. 그럼 [math]\displaystyle{ p\mid a_1a_2\cdots a_n }[/math]이므로, 적당한 [math]\displaystyle{ i }[/math]에 대해 [math]\displaystyle{ p\mid a_i }[/math]이다. 따라서 [math]\displaystyle{ p }[/math]는 [math]\displaystyle{ a_i }[/math]와 [math]\displaystyle{ m }[/math]을 모두 나누고, 이는 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ a_i }[/math]가 서로소라는 가정에 모순이다.

도움정리 2

양의 정수 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]에 대해, [math]\displaystyle{ m }[/math]이 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]의 각각의 배수이면, [math]\displaystyle{ m }[/math]은 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]의 최소공배수의 배수이다.

증명

[math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]의 최소공배수를 [math]\displaystyle{ L }[/math]이라 하자. 그럼 나눗셈 정리에 의해, [math]\displaystyle{ m=qL+r }[/math]을 만족하는 정수 [math]\displaystyle{ q,r }[/math]이 유일하게 존재한다 (단, [math]\displaystyle{ 0\leq r\lt L }[/math]). 그런데 [math]\displaystyle{ a_i }[/math]는 [math]\displaystyle{ m }[/math]과 [math]\displaystyle{ L }[/math]을 모두 나누므로, [math]\displaystyle{ r }[/math]도 나눠야 한다. 이는 모든 [math]\displaystyle{ i }[/math]에 대해 성립하므로, [math]\displaystyle{ r }[/math]은 [math]\displaystyle{ L }[/math]보다 작은 모든 [math]\displaystyle{ a_i }[/math]의 공배수이고, 이는 [math]\displaystyle{ r=0 }[/math]일 때만 가능하다. 따라서 [math]\displaystyle{ m=qL }[/math]이고, [math]\displaystyle{ m }[/math]은 [math]\displaystyle{ L }[/math]의 배수이다.

도움정리 3

양의 정수 [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]에 대해, [math]\displaystyle{ a_1,a_2,\cdots,a_n }[/math]이 쌍마다 서로소이면, [math]\displaystyle{ \text{lcm}\left(a_1,a_2,\cdots,a_n\right)=a_1a_2\cdots a_n }[/math]이다.

증명은 자명하므로 생략한다.

존재성

[math]\displaystyle{ m=m_1m_2\cdots m_n,\,n_k=m/m_k }[/math]라 정의하자. 도움정리 1로 부터 [math]\displaystyle{ \gcd\left(n_k,m_k\right)=1 }[/math]이다. 따라서, [math]\displaystyle{ s_kn_k+t_km_k=1 }[/math]을 만족하는 정수 [math]\displaystyle{ s_k,t_k }[/math]가 존재한다. 이는 곧, [math]\displaystyle{ s_kn_k\equiv1\pmod{m_k} }[/math]이다. 이제 [math]\displaystyle{ x=a_1n_1s_1+a_2n_2s_2+\cdots+a_nn_ns_n }[/math]이라 하자. 만약 [math]\displaystyle{ j\neq k }[/math]면 [math]\displaystyle{ m_k\mid n_j }[/math]이므로, [math]\displaystyle{ x\equiv a_kn_ks_k\equiv a_k\cdot1\equiv a_k\pmod{m_k} }[/math]이다. 이는 임의의 [math]\displaystyle{ k }[/math]에 대해 성립하므로, [math]\displaystyle{ x }[/math]는 주어진 연립합동식의 한 해임을 알 수 있다.

유일성

[math]\displaystyle{ x,y }[/math]가 주어진 연립합동식의 해라고 가정하자. 그러면 임의의 [math]\displaystyle{ k }[/math]에 대해 [math]\displaystyle{ x\equiv a_k\equiv y\pmod{m_k} }[/math]이고, 따라서 [math]\displaystyle{ x-y\equiv0\pmod{m_k} }[/math]이다. 즉, [math]\displaystyle{ x-y }[/math]는 모든 [math]\displaystyle{ m_k }[/math]의 배수이고, 도움정리 2에 의해 [math]\displaystyle{ \text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right) }[/math]이다. 그런데 [math]\displaystyle{ m_1,m_2,\cdots,m_n }[/math]이 쌍마다 서로소이므로, 도움정리 3에 의해 [math]\displaystyle{ \text{lcm}\left(m_1,m_2,\cdots,m_n\right)=m_1m_2\cdots m_n=m\mid\left(x-y\right) }[/math]. 따라서 [math]\displaystyle{ x\equiv y\pmod m }[/math]. 이는 곧 주어진 연립합동식의 해가 유일함을 의미한다.

예시

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

3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 [math]\displaystyle{ 3\times5\times7=105 }[/math]에 대하여 유일한 해를 가진다. [math]\displaystyle{ m=105,n_1=35,n_2=21,n_3=15 }[/math]라 하자.
[math]\displaystyle{ \begin{align*}n_1s_1\equiv35s_1\equiv2s_1\equiv1\pmod3\\n_2s_2\equiv21s_2\equiv s_2\equiv1\pmod5\\n_3s_3\equiv15s_3\equiv s_3\equiv1\pmod7\end{align*} }[/math]
을 풀면 [math]\displaystyle{ s_1=2,s_2=1,s_3=1 }[/math]가 해임을 알 수 있다. 그러므로 [math]\displaystyle{ x\equiv a_1n_1s_1+a_2n_2s_2+a_3n_3s_3\equiv2\cdot35\cdot 2+3\cdot21\cdot1+2\cdot15\cdot1\equiv233 \equiv23\pmod{105} }[/math]이다.

따라서 [math]\displaystyle{ x\equiv23\pmod{105} }[/math]가 주어진 연립 합동식의 해이다.

추상대수학에서

추상대수학버전의 정리도 존재한다.

● [math]\displaystyle{ k\left[x\right] }[/math] 버전

1. [math]\displaystyle{ k }[/math]가 체이고, [math]\displaystyle{ f\left(x\right),\,f'\left(x\right)\in k\left[x\right] }[/math]가 서로소라면, [math]\displaystyle{ k\left[x\right] }[/math]의 두 원소 [math]\displaystyle{ b\left(x\right),\,b'\left(x\right) }[/math]에 대해, [math]\displaystyle{ c-b\in\left(f\right) }[/math]이고 [math]\displaystyle{ c-b'\in\left(f\right) }[/math]인 [math]\displaystyle{ c\left(x\right)\in k\left[x\right] }[/math]가 존재한다. 더욱이, [math]\displaystyle{ d\left(x\right) }[/math]가 또 다른 해라면, [math]\displaystyle{ c-d\in\left(ff'\right) }[/math].
2. [math]\displaystyle{ k }[/math]가 체이고, [math]\displaystyle{ f\left(x\right),\,g\left(x\right)\in k\left[x\right] }[/math]가 서로소라면, [math]\displaystyle{ k\left[x\right]/\left(f\left(x\right)g\left(x\right)\right)\cong k\left[x\right]\left(f\left(x\right)\right)\times k\left[x\right]/\left(g\left(x\right)\right) }[/math].

● 일반화된 버전

[math]\displaystyle{ R }[/math]이 가환환이고, [math]\displaystyle{ I_1,\,I_2,\,\ldots,\,I_n }[/math]이 쌍끼리 서로소인 아이디얼이라고 하자. 만약 [math]\displaystyle{ a_1,\,a_2,\,\ldots,\,a_n\in R }[/math]이면, [math]\displaystyle{ r+I_i=a_i+I_i,\,\forall i }[/math]를 만족하는 [math]\displaystyle{ r\in R }[/math]이 존재한다.

같이 보기

• 나누어떨어짐
• 모듈러산술
• 환