중국인의 나머지 정리

Chinese remainder theorem (CRT)

 

양의 정수들 $n_1,n_2,\cdots ,n_k$가 $1\le i\ne j\le k$,  $gcd(n_i,n_j)=1$(서로소)를 항상 만족할때, 아래의 연립합동식이 법 $M=n_1{n}_2\cdots n_k$에 대해 유일한 해를 가진다.

$$x\equiv a_1(\mathrm{mod}{n}_1)$$

$$x\equiv a_2(\mathrm{mod}{n}_2)$$

$$⋮$$

$$x\equiv a_k(\mathrm{mod}{n}_k)$$

 

 

증명 ( 존재성과 유일성)

$M=n_1{n}_2\cdots n_k$

$M_i=M/n_i$라고 할 때,

$n_j\ne n_i$인 모든 $n_j$에 대해 $M_i\equiv 0(\mathrm{mod}{n}_j)$  이다.

$gcd(n_i,n_j)=1$이므로 (1외에 공유하는 인수가 없으므로) $gcd(n_i,M_i)=1$이고, 따라서 $M_i\cdot M_i^{-1}\equiv 1(\mathrm{mod}{n}_i)$인 $y_i=M_i^{-1}$가 존재한다.($M_i^{-1}$은 확장 유클리드 알고리즘으로 구할수 있다)

그러므로 항상 $M_i{y}_i{a}_i\equiv a_i(\mathrm{mod}{n}_i)$ 이며, 또한 $M_i{y}_i{a}_i\equiv 0(\mathrm{mod}{n}_j)$이다.

 

정리하면

$$\begin{array}{cccc}{M}_1{y}_1{a}_1\equiv a_1(\mathrm{mod}{n}_1)& M_1{y}_1{a}_1\equiv 0(\mathrm{mod}{n}_2)& \cdots & M_1{M}_1^{-1}{a}_1\equiv 0(\mathrm{mod}{n}_k)\\ M_2{y}_2{a}_2\equiv 0(\mathrm{mod}{n}_1)& M_2{y}_2{a}_2\equiv a_2(\mathrm{mod}{n}_2)& \cdots & M_2{M}_2^{-1}{a}_2\equiv 0(\mathrm{mod}{n}_k)\\ ⋮& ⋮& ⋮& ⋮\\ M_k{y}_k{a}_k\equiv 0(\mathrm{mod}{n}_1)& M_k{y}_k{a}_k\equiv 0(\mathrm{mod}{n}_2)& \cdots & M_k{M}_k^{-1}{a}_k\equiv a_k(\mathrm{mod}{n}_k)\end{array}$$

이므로 세로로 보았을 때 모두 더하면 모든 $i$에 대해

$x\equiv M_1{y}_1{a}_1+M_2{y}_2{a}_2+\cdots +M_k{y}_k{a}_k\equiv M_i{y}_i{a}_i\equiv a_i(\mathrm{mod}{n}_i)$를 만족한다.

따라서 $M_1{y}_1{a}_1+M_2{y}_2{a}_2+\cdots +M_k{y}_k{a}_k$를 해로 가진다.

 

 

 

또다른 해 x와 다른 해 z 가 있을 떄 모든 n_i에 대해 $x-z\equiv 0(\mathrm{mod}{n}_i)$ 이므로  모든 n_i에 대해 $n_i|(x-z)$이다.

$gcd(n_1,n_2,\cdots ,n_k)=1$ 이므로 $lcm(n_1,n_2,\cdots ,n_k)=n_1{n}_2\cdots n_k=M$ 이고,   $M|(x-z)$ 라 할 수 있다. 달리 표현하면 $x-z\equiv 0(\mathrm{mod}M)$ 이므로 $x\equiv z(\mathrm{mod}M)$로 연립합동식의 해가 법M에 대해 유일함을 알 수 있다.

 

활용

$x\equiv a_1(\mathrm{mod}{n}_1)$, $x\equiv a_2(\mathrm{mod}{n}_2)$에서 $a_1=a_2$인경우 이미 연립합동식의 해 이므로 $x\equiv a_1(\mathrm{mod}{n}_1{n}_2)$역시 성립한다. RSA에서 평문이 n값과 서로소가 아니여도 작동함을 증명하는데 사용되기도 한다.