중국인의 나머지 정리

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

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

정의편집

일반적 가환환에 대한 경우편집

어떤   속의 두 아이디얼   를 만족시키면, 이 두 아이디얼을 서로소(영어: coprime)라고 한다.

 가 (곱셈 단위원을 갖는) 가환환이라고 하고,  가 쌍마다 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을

 

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

 
 

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

 

정수환에 대한 경우편집

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

쌍마다 서로소인 음이 아닌 정수  가 주어졌다고 하고,

 

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

 

가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해  이 항상 유일하게 존재한다.

 

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

 

증명편집

여기서는 환이 정수환  인 경우만 증명한다. 각  에 대해,   는 서로소이기 때문에,  인 정수  가 존재한다. 여기에서  라고 놓으면,

 
  ( )

가 성립한다.

여기에서  로 놓으면, 임의의  에 대해  가 성립한다. 즉,  가 바로 구하는 해 중의 하나이다.

이제   속에서의 유일성을 증명하기 위해, 두 해  가 존재한다고 가정하자. 그러면  이므로  는 모든  의 배수이고, 따라서   의 배수이다. 즉,  이므로,   속에서는 항상 유일한 해가 존재한다.

역사편집

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

개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?

정답: 23개.

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

今有物,不知其數。三三數之,賸二;五五數之,賸三;七七數之,賸二。問:物幾何?

答曰:二十三。

術曰:三三數之,賸二,置一百四十;五五數之,賸三,置六十三;七七數之,賸二 ,置三十。并之,得二百三十三,以二百一十減之,即得。凡三三數之,賸一,則置七十;五五數之,賸一,則置二十一;七七數之,賸一,則置十五。一百六以上,以一百五減之,即得。
 
— 《孫子算經》 하권(下卷) 문제 26번

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

 

이 경우, 풀이에 따라

 

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

 
 
 

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

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

참고 문헌편집

같이 보기편집

외부 링크편집