중국인의 나머지 정리

청나라 때 출판된 《손자산경》 사본. 중국인의 나머지 정리는 《손자산경》에서 최초로 언급되었다.

수론과 환론에서, 중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다.

정의

일반적 가환환에 대한 경우

어떤 환 $R$$R$ 속의 두 아이디얼 ${\mathfrak {a}},{\mathfrak {b}}\subset R$${\mathfrak a},{\mathfrak b}\subset R$가 ${\mathfrak {a}}+{\mathfrak {b}}=R$${\mathfrak a}+{\mathfrak b}=R$를 만족시키면, 이 두 아이디얼을 서로소(영어: coprime)라고 한다.

$R$$R$가 (곱셈 단위원을 갖는) 가환환이라고 하고, ${\mathfrak {n}}_{1},\dots ,{\mathfrak {n}}_{k}\subset R$${\mathfrak n}_{1},\dots ,{\mathfrak n}_{k}\subset R$가 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을

${\mathfrak {n}}=\prod _{i=1}^{k}{\mathfrak {n}}_{i}$${\mathfrak n}=\prod _{{i=1}}^{k}{\mathfrak n}_{i}$

라고 놓자. 그렇다면 다음이 성립한다.

${\mathfrak {n}}=\bigcap _{i=1}^{k}{\mathfrak {n}}_{i}$${\mathfrak n}=\bigcap _{{i=1}}^{k}{\mathfrak n}_{i}$

$R/{\mathfrak {n}}\cong \prod _{i=1}^{k}R/{\mathfrak {n}}_{i}$$R/{\mathfrak n}\cong \prod _{{i=1}}^{k}R/{\mathfrak n}_{i}$

여기서, 환 동형사상은 구체적으로 다음과 같다.

$r+{\mathfrak {n}}\mapsto (r+{\mathfrak {n}}_{1},\dots ,r+{\mathfrak {n}}_{k})$$r+{\mathfrak n}\mapsto (r+{\mathfrak n}_{1},\dots ,r+{\mathfrak n}_{k})$

정수환에 대한 경우

일반적 가환환에 대한 중국인의 나머지 정리를 정수의 환 $\mathbb {Z}$$\mathbb {Z}$에 대하여 적용하여, 정수론적인 용어로 쓰면 다음과 같다. 이 경우, 아이디얼은 자연수(음이 아닌 정수)로, 서로소 아이디얼은 서로소 자연수로 번역할 수 있다.

서로소인 음이 아닌 정수 $n_{1},n_{2},\cdots ,n_{k}$$n_{1},n_{2},\cdots ,n_{k}$가 주어졌다고 하고,

$n=\prod _{i=1}^{k}n_{i}$$n=\prod _{{i=1}}^{k}n_{i}$

로 놓자. 그렇다면, 임의의 합동류들의 $k$$k$-튜플

$(a_{1},a_{2},\dots ,a_{k})\in \prod _{i=1}^{k}\mathbb {Z} /n_{i}$$(a_{1},a_{2},\dots ,a_{k})\in \prod _{{i=1}}^{k}{\mathbb Z}/n_{i}$

가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해 $a\in \mathbb {Z} /n$$a\in {\mathbb Z}/n$이 항상 유일하게 존재한다.

$a\equiv a_{i}{\pmod {n_{i}}}\quad \forall i=1,\dots ,k$$a\equiv a_{i}{\pmod {n_{i}}}\quad \forall i=1,\dots ,k$

이에 따라서, 다음과 같은 환 동형사상이 존재한다.

$\mathbb {Z} /n\cong \prod _{i=1}^{k}\mathbb {Z} /n_{i}$${\mathbb Z}/n\cong \prod _{{i=1}}^{k}{\mathbb Z}/n_{i}$

증명

여기서는 환이 정수환 $\mathbb {Z}$$\mathbb {Z}$인 경우만 증명한다. 각 $n_{i}$$n_{i}$에 대해, $n/n_{i}$$n/n_{i}$와 $n_{i}$$n_{i}$는 서로소이기 때문에, $r_{i}n_{i}+s_{i}(n/n_{i})=1$$r_{i}n_{i}+s_{i}(n/n_{i})=1$인 정수 $r_{i},s_{i}$$r_{i},s_{i}$가 존재한다. 여기에서 $e_{i}=s_{i}(n/n_{i})$$e_{i}=s_{i}(n/n_{i})$라고 놓으면,

$e_{i}\equiv 1{\pmod {n_{i}}}$$e_{i}\equiv 1{\pmod {n_{i}}}$

$e_{i}\equiv 0{\pmod {n_{j}}}$$e_{i}\equiv 0{\pmod {n_{j}}}$ ($i\neq j$$i\neq j$)

가 성립한다.

여기에서 $a=\sum _{i}a_{i}e_{i}$$a=\sum _{i}a_{i}e_{i}$로 놓으면, 임의의 $i$$i$에 대해 $a\equiv a_{i}{\pmod {n_{i}}}$$a\equiv a_{i}{\pmod {n_{i}}}$가 성립한다. 즉, $a$$a$가 바로 구하는 해 중의 하나이다.

이제 $\mathbb {Z} /n$$\mathbb {Z} /n$ 속에서의 유일성을 증명하기 위해, 두 해 $x,y$$x,y$가 존재한다고 가정하자. 그러면 $x\equiv a_{i},y\equiv a_{i}{\pmod {n_{i}}}$$x\equiv a_{i},y\equiv a_{i}{\pmod {n_{i}}}$이므로 $x-y$$x-y$는 모든 $n_{i}$$n_{i}$의 배수이고, 따라서 $x-y$$x-y$는 $n_{1}n_{2}\cdots n_{k}=n$$n_{1}n_{2}\cdots n_{k}=n$의 배수이다. 즉, $x\equiv y{\pmod {n}}$$x\equiv y{\pmod n}$이므로, $\mathbb {Z} /n$$\mathbb {Z} /n$ 속에서는 항상 유일한 해가 존재한다.

역사

이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같다.

“	개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가? 정답: 23개. 풀이: 셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다. 今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？ 答曰：二十三。 術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二 ，置三十。并之，得二百三十三，以二百一十減之，即得。凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。	”
	— 《孫子算經》 하권(下卷) 문제 26번

즉, 이는 다음과 같은 연립 합동 방정식에 관한 문제이다.

$x\equiv 2{\pmod {3}}\equiv 3{\pmod {5}}\equiv 2{\pmod {7}}$$x\equiv 2{\pmod 3}\equiv 3{\pmod 5}\equiv 2{\pmod 7}$

이 경우, 풀이에 따라

$x\equiv 23{\pmod {3\cdot 5\cdot 7=210}}$$x\equiv 23{\pmod {3\cdot 5\cdot 7=210}}$

이다. 풀이에서 사용된 수는

$140\equiv 2{\pmod {3}}\equiv 0{\pmod {5}}\equiv 0{\pmod {7}}$$140\equiv 2{\pmod 3}\equiv 0{\pmod 5}\equiv 0{\pmod 7}$

$63\equiv 0{\pmod {3}}\equiv 3{\pmod {5}}\equiv 0{\pmod {7}}$$63\equiv 0{\pmod 3}\equiv 3{\pmod 5}\equiv 0{\pmod 7}$

$30\equiv 0{\pmod {3}}\equiv 0{\pmod {5}}\equiv 2{\pmod {7}}$$30\equiv 0{\pmod 3}\equiv 0{\pmod 5}\equiv 2{\pmod 7}$

이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.

이후 이러한 연립 합동 방정식의 문제의 해법은 1247년 남송의 수학자 진구소(秦九韶)가 저술한 《수서구장》(數書九章)에서 더 일반화되었다.

참고 문헌

• Shen Kangsheng (1988). “Historical development of the Chinese remainder theorem”. 《Archive for History of Exact Sciences》 (영어) 38 (4): 285–305. doi:10.1007/BF00357063. ISSN 0003-9519. JSTOR 41133837. 
• Law Hong Ing (2003년 6월). “The history of the Chinese remainder theorem” (PDF). 《Mathematical Medley》 (영어) (Singapore Mathematical Society) 30 (1): 54–62. 

바깥 고리

• “Chinese remainder theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Eric Wolfgang Weisstein. “Chinese remainder theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 일본인의 정리