중국인의 나머지 정리
수론과 환론에서 중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 쌍마다 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 쌍마다 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다.
정의[편집]
일반적 가환환에 대한 경우[편집]
어떤 환 속의 두 아이디얼 가 를 만족시키면, 이 두 아이디얼을 서로소(영어: coprime)라고 한다.
가 (곱셈 단위원을 갖는) 가환환이라고 하고, 가 쌍마다 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을
라고 놓자. 그렇다면 다음이 성립한다.
여기서, 환 동형사상은 구체적으로 다음과 같다.
정수환에 대한 경우[편집]
일반적 가환환에 대한 중국인의 나머지 정리를 정수의 환 에 대하여 적용하여, 정수론적인 용어로 쓰면 다음과 같다. 이 경우, 아이디얼은 자연수(음이 아닌 정수)로, 쌍마다 서로소 아이디얼은 쌍마다 서로소 자연수로 번역할 수 있다.
쌍마다 서로소인 음이 아닌 정수 가 주어졌다고 하고,
로 놓자. 그렇다면, 임의의 합동류들의 -튜플
가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해 이 항상 유일하게 존재한다.
이에 따라서, 다음과 같은 환 동형사상이 존재한다.
증명[편집]
여기서는 환이 정수환 인 경우만 증명한다. 각 에 대해, 와 는 서로소이기 때문에, 인 정수 가 존재한다. 여기에서 라고 놓으면,
- ()
가 성립한다.
여기에서 로 놓으면, 임의의 에 대해 가 성립한다. 즉, 가 바로 구하는 해 중의 하나이다.
이제 속에서의 유일성을 증명하기 위해, 두 해 가 존재한다고 가정하자. 그러면 이므로 는 모든 의 배수이고, 따라서 는 의 배수이다. 즉, 이므로, 속에서는 항상 유일한 해가 존재한다.
역사[편집]
이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같다.
“ | 개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가? 정답: 23개. 풀이: 셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다. 今有物,不知其數。三三數之,賸二;五五數之,賸三;七七數之,賸二。問:物幾何? 答曰:二十三。 術曰:三三數之,賸二,置一百四十;五五數之,賸三,置六十三;七七數之,賸二 ,置三十。并之,得二百三十三,以二百一十減之,即得。凡三三數之,賸一,則置七十;五五數之,賸一,則置二十一;七七數之,賸一,則置十五。一百六以上,以一百五減之,即得。 |
” |
— 《孫子算經》 하권(下卷) 문제 26번
|
즉, 이는 다음과 같은 연립 합동 방정식에 관한 문제이다.
이 경우, 풀이에 따라
이다. 풀이에서 사용된 수는
이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.
이후 이러한 연립 합동 방정식의 문제의 해법은 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. 2016년 5월 9일에 원본 문서 (PDF)에서 보존된 문서. 2014년 8월 12일에 확인함.
같이 보기[편집]
외부 링크[편집]
- “Chinese remainder theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Chinese remainder theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.