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