중국인의 나머지 정리

Chinese remainder theorem (CRT)

 

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

$$x≡ a_1\pmod{n_1}$$

$$x≡ a_2\pmod{n_2}$$

$$\vdots$$

$$x≡ a_k\pmod{n_k}$$

 

 

증명 ( 존재성과 유일성)

$M=n_1n_2\cdots n_k$

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

$n_j\neq n_i$인 모든 $n_j$에 대해 $M_i ≡ 0 \pmod{n_j}$  이다.

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

그러므로 항상 $M_i y_i a_i ≡ a_i\pmod{n_i}$ 이며, 또한 $M_i y_i a_i ≡ 0 \pmod{n_j}$이다.

 

정리하면

\begin{array}{c|c|c|c}
M_1 y_1 a_1 ≡ a_1\pmod{n_1}    &M_1 y_1 a_1 ≡ 0   \pmod{n_2}
&\cdots    &M_1 M_1^{-1} a_1 ≡ 0   \pmod{n_k} \\\hline
M_2 y_2 a_2 ≡ 0   \pmod{n_1}    &M_2 y_2 a_2 ≡ a_2\pmod{n_2}
&\cdots    &M_2 M_2^{-1} a_2 ≡ 0   \pmod{n_k} \\\hline
\vdots  &\vdots  &\vdots  &\vdots \\\hline
M_k y_k a_k ≡ 0   \pmod{n_1}    &M_k y_k a_k ≡ 0   \pmod{n_2}
&\cdots    &M_k M_k^{-1} a_k ≡ a_k\pmod{n_k}\\
\end{array}

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

$x ≡ M_1 y_1 a_1 + M_2 y_2 a_2 +\cdots +M_k y_k a_k ≡ M_i y_i a_i ≡ a_i\pmod{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 ≡ 0 \pmod{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 ≡ 0 \pmod{M}$ 이므로 $x ≡ z \pmod{M}$로 연립합동식의 해가 법M에 대해 유일함을 알 수 있다.

 

활용

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