5. 중국인의 나머지정리, 선형연립합동식

5. 중국인의 나머지정리, 선형연립합동식

중국인의 나머지정리(Chinese Remainder Theorem)

$n_{1},\,n_{2},\,\cdots,\,n_{r}\in\mathbb{N}\,(\text{gcd}(n_{i},\,n_{j})=1,\,(i\neq j))$라 하자. 그러면 다음의 연립합동식

$$\begin{align*}x&\equiv a_{1}\,(\text{mod}\,n_{1})\\x&\equiv a_{2}\,(\text{mod}\,n_{2})\\&\vdots\\x&\equiv a_{r}\,(\text{mod}\,n_{r})\end{align*}$$ 은 법 $n_{1}n_{2}\cdots n_{r}$로 유일한 해를 갖는다.

증명:

$$n=n_{1}n_{2}\cdots n_{r},\,N_{k}=\frac{n}{n_{k}}=n_{1}n_{2}\cdots n_{k-1}n_{k+1}\cdots n_{r}$$ 이라고 하자. $\text{gcd}(n_{i},\,n_{j})=1\,(i\neq j)$이므로 $\text{gcd}(n_{k},\,N_{k})=1$이고, 따라서 1차합동식 $N_{k}x\equiv1\,(\text{mod}\,n_{k})$의 해 $x_{k}$가 존재한다($N_{k}x_{k}\equiv1\, (\text{mod}\,n_{k})$).

$$\overline{x}=a_{1}N_{1}x_{1}+\cdots+a_{r}N_{r}x_{r}$$ 이라고 하자. $$\overline{x}\equiv a_{1}N_{1}x_{1}\equiv a_{1}\,(\text{mod}\,n_{1}),\,\overline{x}\equiv a_{2}N_{2}x_{2}\equiv a_{2}\,(\text{mod}\,n_{2}),\,\cdots,\,\overline{x}\equiv a_{r}N_{r}x_{r}\equiv a_{r}\,(\text{mod}\,n_{r})$$ 이므로 $\overline{x}$는 연립합동식의 해가 된다.

해가 유일함을 보이자. $x'$이 연립합동식의 또다른 해라고 하자. 그러면 $\overline{x}\equiv x'\,(\text{mod}\,n_{k})$이고 $n_{k}|\overline {x}-x'$이므로 $n_{1}n_{2}\cdots n_{r}|\overline{x}-x'$이고 따라서 $\overline{x}\equiv x'\,(\text{mod}\,n_{1}n_{2}\cdots n_{r})$이다.

다음의 연립합동식의 해를 구하자.

$$\begin{align*}x&\equiv2\,(\text{mod}\,3)\\x&\equiv3\,(\text{mod}\,5)\\x&\equiv2\,(\text{mod}\,7)\end{align*}$$ $a_{1}=2,\,a_{2}=3,\,a_{3}=2$, $n_{1}=3,\,n_{2}=5,\,n_{3}=7$이므로, $n=3\cdot5\cdot7=105$, $\displaystyle N_{1}=\frac{n}{n_{1}}=35,\,N_{2}=\frac{n}{n_{2}}=21,\,N_{3}=\frac{n}{n_{3}}=15$이고, $$\begin{align*}(3\cdot11+2)x_{1}&\equiv1\,(\text{mod3})\\(5\cdot4+1)x_{2}&\equiv1\,(\text{mod}\,5)\\(7\cdot2+1)x_{3}&\equiv1\,(\text{mod}\,7)\end{align*}$$ 이므로 $$\begin{align*}2x_{1}&\equiv1\,(\text{mod}\,3)\\x_{2}&\equiv1\,(\text{mod}\,5)\\x_{3}&\equiv1\,(\text{mod}\,7)\end{align*}$$ 이고 $2x_{1}\equiv1\,(\text{mod}\,3)$은 $x_{1}\equiv2\,(\text{mod}\,3)$과 같다. 따라서 이 연립합동식의 해는 $$\overline{x}=2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=233\equiv23\,(\text{mod}\,105)$$ 이다.

합동식 $17x\equiv9\,(\text{mod}\,276)$의 해를 구하자. $276$은 큰 숫자이고 $276=3\cdot4\cdot23$이므로 이 합동식을 다음의 연립합동식으로 나타낼 수 있다.

$$\begin{align*}17x&\equiv9\,(\text{mod}\,3)\\17x&\equiv9\,(\text{mod}\,4)\\17x&\equiv9\,(\text{mod}\,23)\end{align*}$$ $17=3\cdot5+2=4\cdot4+1$이므로 합동식 $17x\equiv 9\,(\text{mod}\,3)$과 $17x\equiv9\,(\text{mod}\,4)$는 $x\equiv0\,(\text{mod}\,3)$, $x\equiv1\,(\text{mod}\,4)$와 같다.

$x\equiv0\,(\text{mod}\,3)$이므로 $x=3k\,(k\in\mathbb{Z})$이고, 이 $x$를 합동식 $x\equiv1\,(\text{mod}\,4)$에 대입해면, 합동식 $3k\equiv1\,(\text{mod}\,4)$를 얻고 $k\equiv3\,(\text{mod}\,4)$이므로 $k=4j+3\,(j\in\mathbb{Z})$이다.

$x=3k=3(4j+3)=12j+9$이고, 이 $x$를 합동식 $17x\equiv9\,(\text{mod}\,23)$에 대입하면, 합동식 $204j\equiv-144\,(\text{mod}\,23)$을 얻고,

$$204=23\cdot8+20,\,144=23\cdot60+6$$ 이므로 $20j\equiv-6\,(\text{mod}\,23)$이고, $\text{gcd}(20,\,23)=1|-6$이므로 $10j\equiv-3\,(\text{mod}\,23)$이고 $x\equiv(-3)7=-21\equiv2\,(\text{mod}\,23)$이다. 그러면 $j=23t+2\,(t\in\mathbb{Z})$이고 $x=276t+33$이므로 따라서 이 합동식의 해는 $x\equiv33\,(\text{mod}\,276)$이다.

연립합동식

$$\begin{cases}ax+by\equiv r\,(\text{mod}\,n)&\\cx+dy\equiv s\,(\text{mod}\,n)&\end{cases}$$ 은 $\text{gcd}(ad-bc,\,n)=1$이면, 법 $n$으로 유일한 해를 갖는다.

증명: 합동식 $adx+bdy\equiv rd\,(\text{mod}\,n)$과 $bcx+bdy\equiv sd\,(\text{mod}\,n)$을 서로 빼면 $(ad-bc)x\equiv rd-sb\,(\text{mod}\,n)$이고, $\text{gcd}(ad-bc,\,n)=1$이므로 $t\in\mathbb{Z}$가 존재해서 $(ad-bc)t\equiv1\,(\text{mod}\,n)$이다. 그러면 $x\equiv t(rd-sb)\,(\text{mod}\,n)$이고, 같은 방법으로 $y\equiv t(as-cr)\,(\text{mod}\,n)$을 얻는다.

연립합동식

$$\begin{cases}7x+3y\equiv10\,(\text{mod}\,16)&\\2x+5y\equiv9\,(\text{mod}\,16)\end{cases}$$ 의 해를 구하자. $7\cdot5-3\cdot2=35-6=29$이고, $\text{gcd}(25,\,16)=1$이므로, 이 연립합동식의 해는 존재한다.

합동식 $35x+15y\equiv50\,(\text{mod}\,16)$과 $6x+15y\equiv27\,(\text{mod}\,16)$을 서로 빼면 $29x\equiv23\,(\text{mod}\,16)$이고 $13x\equiv7\,(\text{mod}\,16)$, $-3x\equiv7\,(\text{mod}\,16)$, $-15x=x\equiv7\cdot5=35\equiv3\,(\text{mod}\,3)$이다.

합동식 $14x+6y\equiv20\,(\text{mod}\,16)$과 $14x+35y\equiv63\,(\text{mod}\,16)$을 서로 빼면 $29y\equiv43\,(\text{mod})\,16$이고, $13y\equiv11\,(\text{mod}\,16)$이므로 $y\equiv11\cdot5=55\equiv7\,(\text{mod}\,16)$이고 따라서 $y\equiv7\,(\text{mod}\,16)$이다.

참고자료

Elementary Number Theory 7th edition, Burton, McGraw-Hill