중국인의 나머지 정리

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

정리

서로 소인 자연수 $n_{1},n_{2},\cdots ,n_{k}$ 와 임의의 정수 $a_{1},a_{2},\cdots ,a_{k}$ 가 있을 때, 임의의 $i$ ( $1\leq i\leq 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\neq 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 모듈로 내에서는 항상 유일한 해가 존재한다.