중국인의 나머지 정리

중국인의 나머지 정리(中國人-定理, 영어: 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_i$ 와 $n_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-y$ 는 $n_1 n_2 \cdots n_k = N$ 의 배수이다. 즉, $x \equiv y \pmod N$ 이므로 N 모듈로 내에서는 항상 유일한 해가 존재한다.