중국인의 나머지 정리

중국인의 나머지 정리는 연립 합동식을 하나의 합동식으로 만드는 것에 대한 정리로, 정수론에서 중요한 위치를 차지한다.

정리

서로 소인 자연수 $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 모듈로 내에서는 항상 유일한 해가 존재한다.

같이 보기

• 일본인의 정리