중국인의 나머지 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 연립 합동식을 하나의 합동식으로 만드는 것에 대한 정리로, 정수론에서 중요한 위치를 차지한다.

정리[편집]

서로 소자연수 n_1, n_2, \cdots, n_k와 임의의 정수 a_1, a_2, \cdots, a_k가 있을 때, 임의의 i(1 \le i \le k)에 대해

x \equiv a_i \pmod {n_i}

로 표현되는 변수 x의 연립 합동 방정식에 대해, 이 방정식이 성립하는 값 x=a가 항상 존재하며, 또한 그 값은 n_1 n_2 \cdots n_k 모듈로 안에서 유일하게 존재한다. 즉, 방정식의 해는 모두 x \equiv a \pmod {n_1 n_2 \cdots n_k}로 표현가능하다.

증명과 계산 방법[편집]

N = n_1 n_2 \cdots n_k이라고 놓는다. 각 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가 바로 구하는 해 중의 하나이다.

이제 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이므로 N 모듈로 내에서는 항상 유일한 해가 존재한다.

역사[편집]

이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장한다. 이후 1247년 남송의 수학자 진구소(秦九韶)가 저술한 《수서구장》(數書九章)에서 더 일반화되었다.

같이 보기[편집]