중국인의 나머지 정리
Published:
부분분수 분해
미적분학에서 제일 어려운 (혹은 대수적으로 번거로운) 주제를 들자면 부분분수 분해가 있을 것이다.
\[\frac{x}{(x+1)(x+2)(x+3)}=-\frac12\frac{1}{x+1}+\frac{2}{x+2}-\frac32\frac{1}{x+3}.\]물론 그 이면의 대수학은 분수의 통분에서 시작할 것이다.
\[x = -\frac12(x+2)(x+3) + 2(x+1)(x+3) - \frac32(x+1)(x+2).\]여기서 각 항은 계수를 제하면 $(x+1)$, $(x+2)$, $(x+3)$ 중 하나를 빼고 모조리 곱한 형태를 취하고 있다. 그리고 이러한 꼴의 곱을 이용하는 상황이 하나 더 있다.
중국인의 나머지 정리
정수론에서 익히 알려진 중국인의 나머지 정리 는 다음과 같이 기술된다.
1보다 큰 정수 $m_1,\cdots,m_k$가 서로 소, 곧 모든 $i\neq j$에 대해 $(m_i,m_j)=1$라 하자. 임의의 연립합동방정식
\[x\equiv a_1 \mod m_1,\] \[x\equiv a_2 \mod m_2,\] \[\ldots\] \[x\equiv a_k \mod m_k\]에는, $M=m_1\cdot\ldots\cdot m_k$에 대해, 유일한 해 $x\equiv a\mod M$가 있다.
증명은 대강 스케치하면 이런 식이다.
정수 $M_j$를 $M_j=m_1\cdot\ldots\cdot\widehat{m}_j\cdot\ldots\cdot m_k$, 곧 $m_1$, …, $m_k$를 곱하되 $m_j$를 뺀 것으로 쓰자. 그러면 $M_j$는 $m_j$와 서로 소이므로 mod $m_j$로 modular inverse $e_j$를 가진다.
그러면 $a=e_1M_1a_1+e_2M_2a_2+\cdots+e_kM_ka_k$라 잡으면 원하던 합동방정식의 해가 된다. 왜냐하면…
그리고 이어지는 증명은 실제로 제시한 $a$가 원하던 숫자임을 보이는 과정이고, 나아가 왜 $a$가 유일한 해인가에 대한 논거가 된다.
이 증명을 부분분수 분해와 엮어서 재해석하고자 한다.
예시
중국인의 나머지 정리는, 사실 응용하기에 따라서 갯수 세기에 적용할 수 있다. 가령 이런 식이다.
60개 이내의 물건 더미를
- 셋씩 묶어 셌더니 나머지가 없고,
- 넷씩 묶어 셌더니 나머지가 3이며,
- 다섯씩 묶어 셋더니 나머지가 2였다.
물건의 갯수를 구하라.
즉, 합동방정식으로 쓰면 $x\equiv 0\mod 3$, $x\equiv 3\mod 4$, $x\equiv 2\mod 5$를 푸는 것이다. 당연히 앞서 중국인의 나머지 정리를 응용해 풀 수도 있지만, 여기서는 일부러 어렵게 부분분수 분해를 동원해서 풀 것이다.
먼저 다음 부분분수 분해를 생각하자.
\[\frac{1}{(x+3)(x+4)(x+5)}=\frac12\frac{1}{x+3}-\frac{1}{x+4}+\frac12\frac{1}{x+5}.\]여기에 $x=0$을 넣으면 그저 $\frac1{60}$을 좀 복잡하게 쓰는 법을 얻는다.
\[\frac1{60}=\frac12\cdot\frac13 - \frac14 + \frac12\cdot \frac15.\]한편으로, 2의 mod 3 inverse는 2이고, 2의 mod 5 inverse는 3이기에, $\frac12$는 다음과 같은 방법으로 쓸 수 있다.
\[\frac12 = 2 + 3z_3,\] \[\frac12 = 3 + 5z_5.\](여기서 $z_3=-\frac12$, $z_5=-\frac12$이다.)
따라서 이들을 반영하면
\[\frac1{60} = \frac12\cdot\frac13 - \frac14 + \frac12\cdot\frac15\] \[=\frac{2+3z_3}{3}-\frac14 +\frac{3+5z_5}{5}\] \[=\frac23-\frac14+\frac35 + (z_3+z_5)\]로 다시 쓰인다. 이 때 $z_3+z_5=-1\in\mathbb{Z}$이므로, 유리수 위에서 다음을 얻는다.
\[\frac{1}{60} \equiv 2\cdot\frac13 - \frac14 + 3\cdot\frac15\mod 1.\](즉 양변의 차이가 정수라는 말이다.)
이게 원래 문제와 어떻게 엮일까? 물건 개수를 $x$라 쓰면, $x$는 정수이므로 다음을 안다.
\[\frac{x}{60} \equiv 2\cdot\frac{x}{3} - \frac{x}{4} + 3\cdot\frac{x}{5}\mod 1.\]그러면 주어진 조건, $x\equiv 0\mod 3$, $x\equiv 3\mod 4$, $x\equiv 2\mod 5$은 다음과 같이 번역할 수 있다.
\[\frac{x}{3}\equiv 0\mod 1;\] \[\frac{x}{4}\equiv\frac34\mod 1;\] \[\frac{x}{5}\equiv\frac25\mod 1.\]그러므로
\[\frac{x}{60} \equiv 2\cdot\frac{x}{3} - \frac{x}{4} + 3\cdot\frac{x}{5}\mod 1\] \[\equiv 2\cdot 0 - \frac34 + 3\cdot\frac25=\frac{9}{20}\mod 1\]을 얻는다. 그러니까 양변에 60을 곱하면
\[x\equiv 27\mod 60\]으로 풀 수 있는 것이고.
곧, 부분분수 분해와 약간의 modular arithmetic을 조합해, (1) $\frac1{60}$ (또는 추상적으로, $\frac1M$)을 mod 1로 $\frac13$, $\frac14$, $\frac15$ (혹은 $\frac1{m_1},\ldots,\frac1{m_k}$의) 조합으로 쓸 수 있고, (2) 이것의 양변에 $x$를 (합동방정식의 미지수를) 곱해 아예 $\frac{x}{60}$이 mod 1로 무엇과 같은지를 직접 계산할 수 있다.
Modular Inverse를 배제할 수 있을까?
심지어 일부 경우에는, 굳이 modular inverse까지 도입하지 않아도 된다. 가령 화두에 제시한
$x\equiv 0\mod 3$, $x\equiv 3\mod 4$, $x\equiv 2\mod 5$를 푸시오.
도
$\frac1{60}=\frac12\cdot\frac13 - \frac14 + \frac12\cdot\frac15$ (유리수로서 같음)
만 써서
$\frac{x}{60}=\frac12\cdot\frac{x}{3} - \frac{x}4 + \frac12\cdot\frac{x}5\equiv \frac12\cdot 0-\frac34+\frac12\cdot\frac25=-\frac{11}{20}\mod 1$
을 보일 수 있다. 이하 양변에 60을 곱해서 $x\equiv 27\mod 60$을 구하는 것은 그렇게 어렵지 않다.
다만,
$x\equiv 1\mod 3$, $x\equiv 3\mod 4$, $x\equiv 2\mod 5$를 푸시오.
의 경우 으레 직관적으로
$\frac{x}{60}=\frac12\cdot\frac{x}3-\frac{x}4+\frac12\cdot\frac{x}5\equiv\frac12\cdot\frac13 - \frac34 + \frac12\cdot\frac25=\frac{37}{60}-1\mod 1$
로 풀어 볼 수 있겠다. 그러나 막상 $x\equiv 37\mod 60$은 $37\equiv 1\mod 4$인 등의 이유로 답이 아니다. 애초에 $\frac12\cdot\frac{x}3\equiv\frac12\cdot\frac13\mod 1$로 보는 데에서 꼬인 탓인데, 이를 무마하기 위해 $x\equiv 4\mod 3$으로 우회해서
$\frac{x}{60}=\frac12\cdot\frac{x}3-\frac{x}4+\frac12\cdot\frac{x}5\equiv\frac12\cdot\frac43 - \frac34 + \frac12\cdot\frac25=\frac{7}{60}\mod 1$
에서 얻은 $x\equiv 7\mod 60$은 바른 답이다.
앞서 modular inverse를 활용하여 보인
$\frac1{60}\equiv 2\cdot\frac13 - \frac14 + 3\cdot\frac15\mod 1$
은 결국 이러한 우회를 고려하지 않기 위해 만들어낸 것이라 이해할 수 있겠다.
일반화
일반적으로는 다음 사실로부터 출발한다. 여간한 기호는 앞서 중국인의 나머지 정리를 증명할 때의 기호에서 이어간다.
정수 $\widetilde{M}_j=(-m_j+m_1)\cdot\ldots\cdot\widehat{(-m_j+m_j)}\cdot\ldots\cdot(-m_j+m_k)$을 생각하자. 그러면 $M_j\equiv\widetilde{M}_j\mod m_j$이다.
나아가, $e_j$는 mod $m_j$로 modular inverse of $\widetilde{M}_j$이기도 하다.
점 ${-m_1,\cdots,-m_k}$에 대해 Lagrange interpolation polynomial를 쓰면, 다음과 같다.
\[\ell_{-m_j}(x)=\frac{1}{\widetilde{M}_j}\prod_{i\neq j}(x+m_i).\]또한, 다항식 1에 대한 Lagrange interpolation formula
\[1=\ell_{-m_1}(x)+\cdots+\ell_{-m_k}(x)\]의 양변을 $\prod_{i=1}^k(x+m_i)$로 나누면 다음 부분분수 분해를 얻는다.
\[\frac{1}{\prod_{i=1}^k(x+m_i)}=\sum_{j=1}^k\frac{1}{\widetilde{M}_j}\frac{1}{x+m_j}.\]여기에 $x=0$을 넣으면
\[\frac{1}{M}=\sum_{j=1}^k\frac{1}{\widetilde{M}_j}\cdot\frac{1}{m_j}\]을 얻는다. 이제 다음이 중국인의 나머지 정리에서 따른다.
\begin{equation} \label{eqn:modular-fraction} \frac{1}M\equiv\sum_{j=1}^k\frac{e_j}{m_j}\mod 1. \end{equation}
(딱히 $1/\widetilde{M}_j\equiv e_j\mod m_j$에서 따르는 결과로는 아닌 것으로 보인다.) 이는 중국인의 나머지 정리에서 제시하는 합동방정식 $x\equiv 1\mod m_j$, $j=1,\cdots,k$의 해가
\[x\equiv 1 \equiv \sum_{j=1}^ke_jM_j\mod M\]이고, 이것이 \eqref{eqn:modular-fraction}과 동치이기 때문이다.
이를 응용하여, 만일 연립합동방정식
$ x\equiv a_1 \mod m_1,$
$ x\equiv a_2 \mod m_2,$
$ \ldots $
$ x\equiv a_k \mod m_k$
이 주어지면,
\[\frac{x}{M}\equiv\sum_{j=1}^ke_j\frac{a_j}{m_j}\mod 1\]이 따르며, 특히 양변에 $M$을 곱하면
\[x \equiv \sum_{j=1}^ke_jM_ja_j(=a)\mod M\]이 따른다. 결국 \eqref{eqn:modular-fraction}의 증명이 중국인의 나머지 정리의 증명 그 자체가 되는 셈이다. (즉 $a_j=1$, $j=1,\cdots,k$인 경우만 잘 다루면 따로 임의의 경우 $a=\sum e_jM_ja_j$에 대해 해로서 적용되고 유일한가를 논할 이유까지는 없는 것이다.)
Update Log
- 211208: Created
- 220226: 후속 포스트