중국인의 나머지 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Sun_Zi_Suanjing.JPG|섬네일|[[청나라]] 때 출판된 《[[손자산경]]》 사본. 중국인의 나머지 정리는 《손자산경》에서 최초로 언급되었다.]]
[[수론]]과 [[환론]]에서 '''중국인의 나머지 정리'''(中國人-定理, {{llang|en|Chinese remainder theorem}})는 [[서로소 아이디얼]]들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 서로소 자연수들에 대한 연립 [[합동식]]의 해의 유일한 존재에 대한 정리이다.

== 정의 ==
=== 일반적 가환환에 대한 경우 ===
어떤 [[환 (수학)|환]] <math>R</math> 속의 두 아이디얼 <math>\mathfrak a,\mathfrak b\subset R</math>가 <math>\mathfrak a+\mathfrak b=R</math>를 만족시키면, 이 두 아이디얼을 '''서로소'''({{llang|en|coprime}})라고 한다.

<math>R</math>가 (곱셈 단위원을 갖는) [[가환환]]이라고 하고, <math>\mathfrak n_1,\dots,\mathfrak n_k\subset R</math>가 서로소 [[아이디얼]]들이라고 하자. 또한, 이 아이디얼들의 곱을
:<math>\mathfrak n=\prod_{i=1}^k\mathfrak n_i</math>
라고 놓자. 그렇다면 다음이 성립한다.
:<math>\mathfrak n=\bigcap_{i=1}^k\mathfrak n_i</math>
:<math>R/\mathfrak n\cong\prod_{i=1}^k R/\mathfrak n_i</math>
여기서, 환 동형사상은 구체적으로 다음과 같다.
:<math>r+\mathfrak n\mapsto(r+\mathfrak n_1,\dots,r+\mathfrak n_k)</math>

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

서로소인 음이 아닌 정수 <math>n_1, n_2, \cdots, n_k</math>가 주어졌다고 하고,
:<math>n=\prod_{i=1}^kn_i</math>
로 놓자. 그렇다면, 임의의 합동류들의 <math>k</math>-[[튜플]]
:<math>(a_1,a_2,\dots,a_k)\in\prod_{i=1}^k\mathbb Z/n_i</math>
가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해 <math>a\in\mathbb Z/n</math>이 항상 유일하게 존재한다.
:<math>a\equiv a_i\pmod{n_i}\quad\forall i=1,\dots, k</math>
이에 따라서, 다음과 같은 환 동형사상이 존재한다.
:<math>\mathbb Z/n\cong\prod_{i=1}^k\mathbb Z/n_i</math>

== 증명 ==
여기서는 환이 정수환 <math>\mathbb Z</math>인 경우만 증명한다. 각 <math>n_i</math>에 대해, <math>n/n_i</math>와 <math>n_i</math>는 서로소이기 때문에, <math>r_i n_i + s_i (n/n_i) = 1</math>인 정수 <math>r_i, s_i</math>가 존재한다. 여기에서 <math>e_i = s_i (n/n_i)</math>라고 놓으면,
:<math>e_i \equiv 1 \pmod {n_i}</math>
:<math>e_i \equiv 0 \pmod {n_j}\qquad(i \ne j)</math>
가 성립한다.

여기에서 <math>a = \sum_i a_i e_i</math>로 놓으면, 임의의 <math>i</math>에 대해 <math>a \equiv a_i \pmod {n_i}</math>가 성립한다. 즉, <math>a</math>가 바로 구하는 해 중의 하나이다.

이제 <math>\mathbb Z/n</math> 속에서의 유일성을 증명하기 위해, 두 해 <math>x, y</math>가 존재한다고 가정하자. 그러면 <math>x \equiv a_i, y \equiv a_i \pmod {n_i}</math>이므로 <math>x-y</math>는 모든 <math>n_i</math>의 배수이고, 따라서 <math>x-y</math>는 <math>n_1 n_2 \cdots n_k = n</math>의 배수이다. 즉, <math>x \equiv y \pmod n</math>이므로, <math>\mathbb Z/n</math> 속에서는 항상 유일한 해가 존재한다.

== 역사 ==
[[파일:Sun Tzu Chinese remainder theorem.svg|섬네일|《손자산경》 하권(下卷) 문제 26번의 해]]
이 정리는 원래 5세기 [[남북조 시대]]의 중국 수학서 《[[손자산경]]》([[:wikisource:zh:孫子算經|孫子算經]])에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같다.
{{인용문2|개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?


정답: 23개.


풀이: 셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다.


{{lang
|lzh
|今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？


答曰：二十三。


術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二 ，置三十。并之，得二百三十三，以二百一十減之，即得。凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。
}}
|《[[:wikisource:zh:孫子算經|孫子算經]]》 하권(下卷) 문제 26번}}
즉, 이는 다음과 같은 연립 합동 방정식에 관한 문제이다.
:<math>x\equiv2\pmod3\equiv3\pmod5\equiv2\pmod7</math>
이 경우, 풀이에 따라
:<math>x\equiv23\pmod{3\cdot5\cdot7=105}</math>
이다. 풀이에서 사용된 수는
:<math>140\equiv 2\pmod3\equiv0\pmod5\equiv0\pmod7</math>
:<math>63\equiv 0\pmod3\equiv3\pmod5\equiv0\pmod7</math>
:<math>30\equiv 0\pmod3\equiv0\pmod5\equiv2\pmod7</math>
이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.

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

== 참고 문헌 ==
* {{저널 인용|제목=Historical development of the Chinese remainder theorem|저자=Shen Kangsheng|저널=Archive for History of Exact Sciences|jstor=41133837|권=38|호=4|날짜=1988|쪽=285–305|doi=10.1007/BF00357063|issn=0003-9519|언어=en}}
* {{저널 인용|제목=The history of the Chinese remainder theorem|저자=Law Hong Ing|권=30|호=1|날짜=2003-06|저널=Mathematical Medley|출판사=Singapore Mathematical Society|url=http://sms.math.nus.edu.sg/smsmedley/Vol-30-1/The%20History%20of%20the%20Chinese%20Reminder%20Theorem%20%28Law%20Huang%20lng%29.pdf|쪽=54–62|언어=en|확인날짜=2014-08-12|보존url=https://web.archive.org/web/20160509020540/http://sms.math.nus.edu.sg/smsmedley/Vol-30-1/The%20History%20of%20the%20Chinese%20Reminder%20Theorem%20(Law%20Huang%20lng).pdf|보존날짜=2016-05-09|url-status=dead}}

== 같이 보기 ==
* [[일본인의 정리]]
* [[소인수 알고리즘]]

== 외부 링크 ==
* {{eom|title=Chinese remainder theorem}}
* {{매스월드|id=ChineseRemainderTheorem|title=Chinese remainder theorem}}

{{전거 통제}}

[[분류:수론 정리]]
[[분류:가환대수학]]
[[분류:중국 수학]]
[[분류:모듈러 산술]]