중국인의 나머지 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
청나라 때 출판된 《손자산경》 사본. 중국인의 나머지 정리는 《손자산경》에서 최초로 언급되었다.

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

정의[편집]

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

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

R가 (곱셈 단위원을 갖는) 가환환이라고 하고, \mathfrak n_1,\dots,\mathfrak n_k\subset R가 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을

\mathfrak n=\prod_{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\mapsto(r+\mathfrak n_1,\dots,r+\mathfrak n_k)

정수환에 대한 경우[편집]

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

서로소인 음이 아닌 정수 n_1, n_2, \cdots, n_k가 주어졌다고 하고,

n=\prod_{i=1}^kn_i

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

(a_1,a_2,\dots,a_k)\in\prod_{i=1}^k\mathbb Z/n_i

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

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_i에 대해, n/n_in_i는 서로소이기 때문에, r_i n_i + s_i (n/n_i) = 1인 정수 r_i, s_i가 존재한다. 여기에서 e_i = s_i (n/n_i)라고 놓으면,

e_i \equiv 1 \pmod {n_i}
e_i \equiv 0 \pmod {n_j} (i \ne j)

가 성립한다.

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

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

역사[편집]

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

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

정답: 23개.

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

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

答曰:二十三。

術曰:三三數之,賸二,置一百四十;五五數之,賸三,置六十三;七七數之,賸二 ,置三十。并之,得二百三十三,以二百一十減之,即得。凡三三數之,賸一,則置七十;五五數之,賸一,則置二十一;七七數之,賸一,則置十五。一百六以上,以一百五減之,即得。

 
— 《孫子算經》 하권(下卷) 문제 26번

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

x\equiv2\pmod3\equiv3\pmod5\equiv2\pmod7

이 경우, 풀이에 따라

x\equiv23\pmod{3\cdot5\cdot7=210}

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

140\equiv 2\pmod3\equiv0\pmod5\equiv0\pmod7
63\equiv 0\pmod3\equiv3\pmod5\equiv0\pmod7
30\equiv 0\pmod3\equiv0\pmod5\equiv2\pmod7

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

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

참고 문헌[편집]

바깥 고리[편집]

같이 보기[편집]