Up

중국인의 나머지 정리

2018년 8월 13일

예제

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

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

\[ 7n + 5 \equiv 13 \pmod{18} \qquad \Rightarrow \qquad 7n \equiv 8 \pmod{18} \]

법 18에 대한 7의 곱셈 역원 13을 양변에 곱합시다. 7과 18이 서로소이므로 존재합니다.

\[ n \equiv 14 \pmod{18} \]

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

\[ x \equiv 103 \pmod{126} \label{eq:merged} \]

식 \eqref{eq:merged}는 연립합동식의 첫 번째와 두 번째 식을 합친 것입니다. 같은 방법으로 세 번째 식까지 합치면 연립합동식의 해를 구할 수 있습니다. $x=126m+103$을 세 번째 식에 대입하면

\[ 126m + 103 \equiv 21 \pmod{29} \qquad\Rightarrow\qquad 126m \equiv 5 \pmod{29} \]

역시 법 29에 대한 126의 곱셈 역원 3을 곱하여 $m$을 구합니다.

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

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

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

중국인의 나머지 정리

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

\[ \gcd(m_i, m_j) = 1 \qquad \text{for } \ i\neq j \]

를 만족할 때, 일차연립합동식

\begin{gathered} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{gathered}

의 해를 구하는 일반적인 알고리즘을 생각할 수 있습니다. 이를 유도하기 전에 유도 과정에 필요한 보조정리 두 가지를 짚고 넘어가겠습니다.

정수 $a$, $b$, $k$에 대해 \[ 1 - ka\left[(ka)^{-1}\bmod{b}\right] = b(b^{-1}\bmod{a}) \] 단, $a^{-1}\bmod{m}$은 법 $m$에 대한 $a$의 곱셈 역원을 의미한다.
곱셈 역원의 정의에 의해 적당한 정수 $l$이 존재하여,
\[ ka\left[(ka)^{-1}\bmod{b}\right] = bl + 1 \]

또는 법 $a$에 대한 합동식으로 쓰면

\[ bl + 1 \equiv 0 \pmod{a} \qquad\Rightarrow\qquad b(-l) \equiv 1 \pmod{a} \]

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

\[ 1 - ka\left[(ka)^{-1}\bmod{b}\right] = b(-l) = b(b^{-1}\bmod{a}) \]

가 성립합니다.

정수 $a$, $b$, $m$에 대해 \[ (a^{-1}\bmod{m})(b^{-1}\bmod{m}) = (ab)^{-1}\bmod{m} \]
\begin{gather} \begin{aligned} a(a^{-1}\bmod{m}) &\equiv 1 \pmod{m} \\ b(b^{-1}\bmod{m}) &\equiv 1 \pmod{m} \end{aligned} \\ \Rightarrow\ ab(a^{-1}\bmod{m})(b^{-1}\bmod{m}) \equiv 1 \pmod{m} \end{gather}

따라서 보조정리가 성립합니다.

제일 처음 두 식부터 합쳐봅시다. $x=m_1k_1+a_1$이라 하고 둘째 식에 대입하면

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

그대로 셋째 식에 또 대입합시다. 중간 과정이 매우 긴데, 결과만 적겠습니다.

\begin{aligned} x =& m_1m_2m_3k_3 + m_2m_3\left[(m_2m_3)^{-1}\bmod{m_1}\right]a_1 \\ &\quad+ m_3m_1\left[(m_3m_1)^{-1}\bmod{m_2}\right]a_2 + m_1m_2\left[(m_1m_2)^{-1}\bmod{m_3}\right]a_3 \end{aligned}

규칙이 보이시나요? $M=m_1m_2\cdots m_3$, $M_i=M/m_i$라 하면 연립합동식의 최종 정답은 아래와 같습니다.

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

이를 중국인의 나머지 정리(chinese remainder theorem, CRT)라고 합니다. 예제 1을 중국인의 나머지 정리로 풀어봅시다.

\begin{gather*} M = 3654 \\ M_1 = 522, \qquad M_2 = 203, \qquad M_3 = 126 \\ M_1^{-1}\bmod{m_1} = 2, \qquad M_2^{-1}\bmod{m_2} = 11, \qquad M_3^{-1}\bmod{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{aligned} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \end{aligned} \label{eq:not-coprime} \]

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

\[ m_1k_1 \equiv a_2 - a_1 \pmod{m_2} \qquad\Rightarrow\qquad m_1k_1 + m_2k_2 = a_2 - a_1 \]

만약 $a_2 - a_1$이 $m_1$과 $m_2$의 최대공약수 $g$의 배수가 아니라면 식 \eqref{eq:not-coprime}의 해는 존재하지 않습니다. 이제 확장 유클리드 호제법으로 적당한 $k_1$의 값을 하나 구했다고 하면($k_0$라고 합시다) $k_1$의 일반해는

\[ 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:: 날짜 계산

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

\begin{aligned} x &\equiv E \pmod{15} \\ x &\equiv S \pmod{28} \\ x &\equiv M \pmod{19} \\ \end{aligned}

중국인의 나머지 정리를 쓰면

\[ x \equiv 6916E + 4845S + 4200M \pmod{7980} \]

BOJ 6064:: 카잉 달력

각 테스트 케이스에 대해 다음 합동식을 만족하는 양의 정수 $k$의 최솟값을 구하면 됩니다.

\begin{aligned} k &\equiv x \pmod{M} \\ k &\equiv y \pmod{N} \end{aligned}

위에서 설명한 대로 $y-x$가 $\gcd(M,N)$의 배수여야 합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

tuple<ll, ll, ll> extended_euclidean(ll a, ll b) {
    if (b == 0)
        return make_tuple(a, 1, 0);
    auto [g, x, y] = extended_euclidean(b, a%b);
    return make_tuple(g, y, x-(a/b)*y);
}

int main(void) {
    ll t, m, n, x, y, k;
    cin >> t;
    while (t--) {
        cin >> m >> n >> x >> y;
        auto [g, k0, _] = extended_euclidean(m, n);

        if ((y - x) % g != 0)
            cout << "-1" << endl;
        else {
            k0 *= (y - x) / g;
            k = (m * k0 + x) % (m * n / g);
            while (k <= 0)
                k += m * n / g;
            cout << k << endl;
        }
    }
    return 0;
}