중국인의 나머지 정리

(중국인의 나머지 정리)

$n_{1},~n_{2},~\cdots ,~n_{r}$을 $i\neq j$에 대해 $gcd(n_{i},~n_{j})=1$인 양의 정수라 하자. 

그러면 연립 선형 합동식

$$\left\{\begin{matrix}
x\equiv a_{1} & (mod~n_{1}) \\
x\equiv a_{2} & (mod~n_{2}) \\
 & \vdots  \\
x\equiv a_{r} & (mod~n_{r}) \\
\end{matrix}\right.$$

은 법 $n_{1}n_{2}\cdots n_{r}$에 대해 유일한 공통 해를 가진다.

 

<해를 구하는 순서>

1. $N=\prod_{i=1}^{r}n_{i}$에 대하여 $N_{i}=\frac{N}{n_{i}}$라 한다.

2. $N_{i}x_{i}\equiv 1~(mod~n_{i})$가 되는 $x_{i}$를 찾는다.

3. $\sum_{i=1}^{r}a_{i}N_{i}x_{i}$은 주어진 연립선형합동식의 법 $n_{1}n_{2}\cdots n_{r}$에 대하여 유일한 공통해이다.

 

ex) 다음 연립 선형 합동식의 해를 구하시오.

$$\left\{\begin{matrix}
x\equiv 2 & (mod~3) \\
x\equiv 3 & (mod~5) \\
x\equiv 2 & (mod~7) \\
\end{matrix}\right.$$

 

sol)

$$\left\{\begin{matrix}
x\equiv 2 & (mod~3) & N_{1}=35 & x_{1}=2 \\
x\equiv 3 & (mod~5) & N_{2}=21 & x_{2}=1 \\
x\equiv 2 & (mod~7) & N_{3}=15 & x_{3}=1 \\
\end{matrix}\right.$$

그러므로 법 $3\cdot 5\cdot 7=105$에 대해 유일한 공통 해 $x=2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1\equiv 23~(mod~105)$을 갖는다.