중국인의 나머지 정리

예제

다음 일차연립합동식을 만족하는 모든 $x$ 를 구하시오.

\begin{aligned} x & \equiv 5 (\mod 7) \\ x & \equiv 13 (\mod 18) \\ x & \equiv 21 (\mod 29) \end{aligned}

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

7 n + 5 \equiv 13 (\mod 18) \Rightarrow 7 n \equiv 8 (\mod 18)

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

n \equiv 14 (\mod 18)

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

\begin{matrix} (1) & x \equiv 103 (\mod 126) \end{matrix}

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

126 m + 103 \equiv 21 (\mod 29) \Rightarrow 126 m \equiv 5 (\mod 29)

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

m \equiv 15 (\mod 29)

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

x \equiv 1993 (\mod 3654)

중국인의 나머지 정리

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

gcd (m_{i}, m_{j}) = 1 for i \neq j

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

\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}

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

정수 $a$ , $b$ , $k$ 에 대해

1 - k a [(k a)^{- 1} mod b] = b (b^{- 1} mod a)

단, $a^{- 1} mod m$ 은 법 $m$ 에 대한 $a$ 의 곱셈 역원을 의미한다.

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

k a [(k a)^{- 1} mod b] = b l + 1

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

b l + 1 \equiv 0 (\mod a) \Rightarrow b (- l) \equiv 1 (\mod a)

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

1 - k a [(k a)^{- 1} mod b] = b (- l) = b (b^{- 1} mod a)

가 성립합니다.

정수 $a$ , $b$ , $m$ 에 대해

(a^{- 1} mod m) (b^{- 1} mod m) = (a b)^{- 1} mod m

\begin{matrix} \begin{aligned} a (a^{- 1} mod m) & \equiv 1 (\mod m) \\ b (b^{- 1} mod m) & \equiv 1 (\mod m) \end{aligned} \\ \Rightarrow a b (a^{- 1} mod m) (b^{- 1} mod m) \equiv 1 (\mod m) \end{matrix}

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

제일 처음 두 식부터 합쳐봅시다. $x = m_{1} k_{1} + a_{1}$ 이라 하고 둘째 식에 대입하면

\begin{aligned} m_{1} k_{1} + a_{1} \equiv a_{2} (\mod m_{2}) \\ \Rightarrow & k_{1} \equiv (m_{1}^{- 1} mod m_{2}) (a_{2} - a_{1}) (\mod m_{2}) \\ \Rightarrow & k_{1} = m_{2} k_{2} + (m_{1}^{- 1} mod m_{2}) (a_{2} - a_{1}) \end{aligned}

\begin{aligned} ∴ x & = m_{1} m_{2} k_{2} + m_{1} (m_{1}^{- 1} mod m_{2}) (a_{2} - a_{1}) + a_{1} \\ = m_{1} m_{2} k_{2} + [1 - m_{1} (m_{1}^{- 1} mod m_{2})] a_{1} + m_{1} (m_{1}^{- 1} mod m_{2}) a_{2} \\ = m_{1} m_{2} k_{2} + m_{2} (m_{2}^{- 1} mod m_{1}) a_{1} + m_{1} (m_{1}^{- 1} mod m_{2}) a_{2} \end{aligned}

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

\begin{aligned} x = & m_{1} m_{2} m_{3} k_{3} + m_{2} m_{3} [(m_{2} m_{3})^{- 1} mod m_{1}] a_{1} \\ + m_{3} m_{1} [(m_{3} m_{1})^{- 1} mod m_{2}] a_{2} + m_{1} m_{2} [(m_{1} m_{2})^{- 1} mod m_{3}] a_{3} \end{aligned}

규칙이 보이시나요? $M = m_{1} m_{2} \dots m_{3}$ , $M_{i} = M / m_{i}$ 라 하면 연립합동식의 최종 정답은 아래와 같습니다.

x \equiv \sum_{i = 1}^{n} M_{i} (M_{i}^{- 1} mod m_{i}) a_{i} (\mod M)

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

\begin{matrix} M = 3654 \\ M_{1} = 522, M_{2} = 203, M_{3} = 126 \\ M_{1}^{- 1} mod m_{1} = 2, M_{2}^{- 1} mod m_{2} = 11, M_{3}^{- 1} mod m_{3} = 3 \\ ∴ x \equiv 522 \times 2 \times 5 + 203 \times 11 \times 13 + 126 \times 3 \times 21 \equiv 1993 (\mod 3654) \end{matrix}

법이 서로소가 아닐 때

일차연립합동식에서 법이 서로소가 아니어도 두 식을 합칠 수 있습니다. $m_{1}$ 과 $m_{2}$ 가 서로소가 아니라고 가정하고 다음 합동식을 봅시다.

\begin{matrix} (2) & \begin{aligned} x & \equiv a_{1} (\mod m_{1}) \\ x & \equiv a_{2} (\mod m_{2}) \end{aligned} \end{matrix}

똑같은 방식으로 $x = m_{1} k_{1} + a_{1}$ 이라 하고 두 번째 식에 대입하면

m_{1} k_{1} \equiv a_{2} - a_{1} (\mod m_{2}) \Rightarrow m_{1} k_{1} + m_{2} k_{2} = a_{2} - a_{1}

만약 $a_{2} - a_{1}$ 이 $m_{1}$ 과 $m_{2}$ 의 최대공약수 $g$ 의 배수가 아니라면 식 $(2)$ 의 해는 존재하지 않습니다. 이제 확장 유클리드 호제법으로 적당한 $k_{1}$ 의 값을 하나 구했다고 하면( $k_{0}$ 라고 합시다) $k_{1}$ 의 일반해는

k_{1} = k_{0} + l \frac{m_{2}}{g}

따라서

x = m_{1} k_{0} + l \frac{m_{1} m_{2}}{g} + a_{1}

또는 $m_{1} m_{2} / g$ 가 $m_{1}$ 과 $m_{2}$ 의 최소공배수이므로

x \equiv m_{1} k_{0} + a_{1} (\mod lcm (m_{1}, m_{2}))

응용

BOJ 1476:: 날짜 계산

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

\begin{aligned} x & \equiv E (\mod 15) \\ x & \equiv S (\mod 28) \\ x & \equiv M (\mod 19) \end{aligned}

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

x \equiv 6916 E + 4845 S + 4200 M (\mod 7980)

BOJ 6064:: 카잉 달력

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

\begin{aligned} k & \equiv x (\mod M) \\ k & \equiv y (\mod 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;
}

Algorithm