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

예제 하나

문제) 다음 일차연립합동식을 만족하는 모든 $x$를 구하시오.\[ \begin{gather}
x \equiv 5 \pmod{7} \\
x \equiv 13 \pmod{18} \\
x \equiv 21 \pmod{29}
\end{gather} \]

풀이) $x$가 첫 번째 식을 만족해야 하므로 $x=7n+5$이라고 쓸 수 있습니다. 이를 두 번째 식에 대입하면

\[ \begin{gather}
7n+5 \equiv 13 \pmod{18}
7n \equiv 8 \pmod{18}
\end{gather} \]

법 18에 대한 7의 곱셈 역원 $7^{-1}=13$을 양변에 곱합시다. (7과 18이 서로소이므로 존재합니다.) 곱셈 역원은 확장 유클리드 호제법을 써서 구하면 됩니다.

\[ 7n \times 13 \equiv 91n \equiv n \equiv 8\times 13 \equiv 14 \pmod{18} \]

따라서 $n=18m+14$로 나타낼 수 있고, 이걸 다시 $x=7n+5$에 대입하면 $x=126m+103$, 즉

\[ x \equiv 103 \pmod{126} \]

결론적으로 첫 번째 식과 두 번째 식을 합쳐서 식 하나로 만들 수 있습니다. 이 식을 세 번째 식과도 합쳐야 합니다. $x=126m+103$를 세 번째 식에 대입하면

\[ \begin{gather}
126m+103 \equiv 21 \pmod{29} \\
126m \equiv -82 \equiv 5 \pmod{29}
\end{gather} \]

법 29에 대한 126의 곱셈 역원 $126^{-1}=3$을 곱합시다. 역시 126과 29가 서로소이기 때문에 역원이 존재합니다.

\[ m \equiv 15 \pmod{29} \]

고로 $m=29k+15$이고, $x=126m+103$에 대입하면 주어진 방정식의 해는 다음과 같습니다. ■

\[ x \equiv 1993 \pmod{3654} \]

중국인의 나머지 정리

위 문제를 푸는 핵심 아이디어는, 법 둘을 고르면 항상 서로소라는 걸 이용해서 곱셈 역원을 구하고 두 합동식을 하나로 합친다는 겁니다. 이걸 일반화해서 $m_1,\ m_2,\ m_3,\ \cdots,\ m_n$이

\[ \mathrm{gcd}(m_i,\ m_j)=1\quad\textrm{for}\quad i\neq j \]

을 만족할 때,

\[ \begin{gather}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
x \equiv a_3 \pmod{m_3} \\
\vdots \\
x \equiv a_n \pmod{m_n}
\end{gather} \]

을 만족하는 모든 $x$는 어떻게 될까요? 먼저 제일 처음 두 식부터 합쳐봅시다. $x=m_1k_1+a_1$이라 하고 둘째 식에 대입하면

\[ \begin{align}
& m_1k_1+a_1 \equiv a_2 \pmod{m_2} \\
\Rightarrow \ & k_1 \equiv (m_1^{-1}\mod{m_2})(a_2-a_1) \pmod{m_2} \\
\Rightarrow \ & k_1 = m_2k_2 + (m_1^{-1}\mod{m_2})(a_2-a_1) \\
\therefore \ & x = m_1m_2k_2 + m_1(m_1^{-1}\mod{m_2})(a_2-a_1)+a_1 \\
\end{align} \]

합동식으로 다시 쓰면

\[ \begin{align}
x &\equiv m_1(m_1^{-1}\mod{m_2})(a_2-a_1)+a_1 \\
&\equiv [1-m_1(m_1^{-1}\mod{m_2})]a_1 + m_1(m_1^{-1}\mod{m_2})a_2 \pmod{m_1m_2}
\end{align} \]

그런데 곱셈 역원의 정의에 의해 적당한 정수 $l$이 존재하여

\[ m_1(m_1^{-1}\mod{m_2}) = m_2l + 1 \]

이고, 법 $m_1$에 대한 합동식으로 만들면

\[ \begin{align}
& m_2l + 1 \equiv 0 \pmod{m_1} \\
\Rightarrow \ & m_2(-l) \equiv 1 \pmod{m_1}
\end{align} \]

이므로 $-l$은 법 $m_1$에 대한 $m_2$의 곱셈 역원입니다. 따라서

\[ 1-m_1(m_1^{-1}\mod{m_2}) = m_2(-l) = m_2(m_2^{-1}\mod{m_1}) \]

이 되어 $x$를 아래와 같이 쓸 수 있습니다.

\[ x = m_1m_2k_2 + m_2(m_2^{-1}\mod{m_1})a_1 + m_1(m_1^{-1}\mod{m_2})a_2 \]

이걸 셋째 식에 대입하면

\[ \begin{align}
& m_1m_2k_2 + m_2(m_2^{-1}\mod{m_1})a_1 + m_1(m_1^{-1}\mod{m_2})a_2 \equiv a_3 \pmod{m_3} \\
\Rightarrow \ & k_2 \equiv [(m_1m_2)^{-1}\mod{m_3}]
[a_3-m_2(m_2^{-1}\mod{m_1})a_1-m_1(m_1^{-1}\mod{m_2})a_2] \pmod{m_3} \\
\Rightarrow \ & k_2 = m_3k_3 + [(m_1m_2)^{-1}\mod{m_3}]
[a_3-m_2(m_2^{-1}\mod{m_1})a_1-m_1(m_1^{-1}\mod{m_2})a_2] \\
\therefore \ & x = m_1m_2m_3k_3 + m_1m_2[(m_1m_2)^{-1}\mod{m_3}] \\
& \qquad \times [a_3-m_2(m_2^{-1}\mod{m_1})a_1-m_1(m_1^{-1}\mod{m_2})a_2] \\
& \qquad +m_2(m_2^{-1}\mod{m_1})a_1 + m_1(m_1^{-1}\mod{m_2})a_2
\end{align} \]

역시 합동식으로 쓰면

\[ \begin{align}
x \equiv & m_1m_2[(m_1m_2)^{-1}\mod{m_3}][a_3-m_2(m_2^{-1}\mod{m_1})a_1-m_1(m_1^{-1}\mod{m_2})a_2] \\
& +m_2(m_2^{-1}\mod{m_1})a_1 + m_1(m_1^{-1}\mod{m_2})a_2 \\
\equiv & \{1-m_1m_2[(m_1m_2)^{-1}\mod{m_3}]\}m_2(m_2^{-1}\mod{m_1})a_1 \\
& + \{1-m_1m_2[(m_1m_2)^{-1}\mod{m_3}]\}m_1(m_1^{-1}\mod{m_2})a_2 \\
& + m_1m_2[(m_1m_2)^{-1}\mod{m_3}]a_3 \pmod{m_1m_2m_3}
\end{align} \]

곱셈 역원의 정의에 의해 적당한 정수 $l$이 존재하여

\[ m_1m_2[(m_1m_2)^{-1}\mod{m_3}] = m_3l + 1 \]

양 변을 $m_1$과 $m_2$로 나눠보면

\[ -l = m_3^{-1}\mod{m_1} = m_3^{-1}\mod{m_2} \]

이므로

\[ 1-m_1m_2[(m_1m_2)^{-1}\mod{m_3}] = m_3(-l) = m_3(m_3^{-1}\mod{m_1}) = m_3(m_3^{-1}\mod{m_2}) \]

따라서

\[ \begin{align}
x \equiv & m_2m_3(m_2^{-1}\mod{m_1})(m_3^{-1}\mod{m_1})a_1 \\
& + m_3m_1(m_3^{-1}\mod{m_2})(m_1^{-1}\mod{m_2})a_2 \\
& + m_1m_2[(m_1m_2)^{-1}\mod{m_3}]a_3 \pmod{m_1m_2m_3}
\end{align} \]

여기서

\[ \begin{align}
& m_2(m_2^{-1}\mod{m_1}) \equiv 1 \pmod{m_1} \qquad \textrm{and} \qquad m_3(m_3^{-1}\mod{m_1}) \equiv 1 \pmod{m_1} \\
\Rightarrow \ & m_2m_3(m_2^{-1}\mod{m_1})(m_3^{-1}\mod{m_1}) \pmod{m_1}
\end{align} \]

이므로

\[ (m_2m_3)^{-1}\mod{m_1} = (m_2^{-1}\mod{m_1})(m_3^{-1}\mod{m_1}) \]

이고, 마찬가지로

\[ (m_3m_1)^{-1}\mod{m_2} = (m_3^{-1}\mod{m_2})(m_1^{-1}\mod{m_2}) \]

이를 대입하면

\[ \begin{align}
x \equiv & m_2m_3[(m_2m_3)^{-1}\mod{m_1})]a_1 \\
& + m_3m_1[(m_3m_1)^{-1}\mod{m_2}]a_2 \\
& + m_1m_2[(m_1m_2)^{-1}\mod{m_3}]a_3 \pmod{m_1m_2m_3}
\end{align} \]

이제 슬슬 규칙이 보이죠. $M=m_1m_2m_3\cdots m_n$이고 $M_i=M/m_i$이라 하면 $n$ 번째 식까지 다 합쳐서 나오는 최종 정답은

\[ x \equiv \sum_{i=1}^n M_i(M_i^{-1}\mod{m_i})a_i \pmod{M} \]

위 식을 중국인의 나머지 정리라고 합니다.

글 첫머리의 예제를 중국인의 나머지 정리로 풀어보자면

\[ \begin{gather}
M=3654 \\
M_1=522, \quad M_2=203, \quad M_3=126 \\
M_1^{-1}\mod{m_1}=2, \quad M_2^{-1}\mod{m_2}=11, \quad M_3^{-1}\mod{m_3}=3 \\
\therefore \ x \equiv 522\times2\times5+203\times11\times13+126\times3\times21 \equiv 1993 \pmod{3654}
\end{gather} \]

법이 서로소가 아닐 때

다음 일차연립합동식에서 $m_1$과 $m_2$가 서로소가 아니라고 해봅시다.

\[ \begin{gather}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2}
\end{gather} \]

똑같은 방식으로 $x=m_1k_1+a_1$이라 하고 두 번째 식에 대입하면

\[ m_1k_1 \equiv a_2-a_1 \pmod{m_2} \]

또는

\[ m_1k_1 + m_2k_2 = a_2-a_1 \]

를 만족하는 정수 $k_1$, $k_2$가 존재해야 합니다. 확장 유클리드 호제법에서 봤던 대로 $m_1$과 $m_2$의 최대공약수가 $a_2-a_1$의 약수일 때에만 $k_1$, $k_2$가 존재합니다. 즉,

\[ a_1 \equiv a_2 \pmod{g} \]

여기서 $g=\mathrm{gcd}(m_1, m_2)$입니다. 이제 확장 유클리드 호제법으로 적당히 $k_1$의 값 하나를 구했다고 하면($k_0$라고 합시다) $k_1$의 일반해는 임의의 정수 $l$에 대해

\[ k_1 = k_0 + l\frac{m_2}{g} \]

따라서

\[ x = m_1k_0 + l\frac{m_1m_2}{g} + a_1 \]

또는 $m_1m_2/g$가 $m_1$과 $m_2$의 최소공배수이므로

\[ x \equiv m_1k_0 + a_1 \pmod{\mathrm{lcm}(m_1,m_2)} \]

응용

BOJ 1476:: 날짜 계산

https://www.acmicpc.net/problem/1476

아래 합동식을 만족하는 양의 정수 $x$의 최솟값을 구하면 됩니다.

\[ \begin{gather}
x \equiv E \pmod{15} \\
x \equiv S \pmod{28} \\
x \equiv M \pmod{19}
\end{gather} \]

중국인의 나머지 정리를 쓰면 $x \equiv 6916E+4845S+4200M \pmod{7980}$입니다.