중국인의 나머지 정리¶

중국인의 나머지 정리(이 글의 나머지 부분에서는 CRT라고 부르겠습니다)는 중국의 수학자 손자(孫子)가 발견하였습니다.

정식화¶

$m = m_1 \cdot m_2 \cdots m_k$라고 합시다. 여기서 $m_i$는 쌍마다 서로소입니다. $m_i$와 함께 다음과 같은 연립 합동식도 주어집니다.

$$\left\{\begin{array}{rcl} a & \equiv & a_1 \pmod{m_1} \\ a & \equiv & a_2 \pmod{m_2} \\ & \vdots & \\ a & \equiv & a_k \pmod{m_k} \end{array}\right.$$

여기서 $a_i$는 주어진 상수입니다. 이때 CRT의 원래 형태는 주어진 연립 합동식이 $m$을 법으로 하여 항상 유일한 해를 가진다는 것입니다.

예를 들어, 다음 연립 합동식은

$$\left\{\begin{array}{rcl} a & \equiv & 2 \pmod{3} \\ a & \equiv & 3 \pmod{5} \\ a & \equiv & 2 \pmod{7} \end{array}\right.$$

$105$를 법으로 하여 해 $23$을 가집니다. $23 \bmod{3} = 2$, $23 \bmod{5} = 3$, $23 \bmod{7} = 2$이기 때문입니다. 모든 해는 $k \in \mathbb{Z}$에 대하여 $23 + 105\cdot k$로 쓸 수 있습니다.

따름정리¶

CRT에 따르면 다음 방정식은

$$x \equiv a \pmod{m}$$

은 다음 연립방정식과 동치입니다.

$$\left\{\begin{array}{rcl} x & \equiv & a_1 \pmod{m_1} \\ & \vdots & \\ x & \equiv & a_k \pmod{m_k} \end{array}\right.$$

(위와 마찬가지로 $m = m_1 m_2 \cdots m_k$이고 $m_i$는 쌍마다 서로소라고 가정합니다.)

두 개의 법에 대한 해법¶

서로소인 $m_1, m_2$에 대하여 두 방정식으로 이루어진 연립 방정식을 생각해 봅시다.

$$ \left\{\begin{align} a &\equiv a_1 \pmod{m_1} \\ a &\equiv a_2 \pmod{m_2} \\ \end{align}\right. $$

우리는 $a \pmod{m_1 m_2}$의 해를 구하고자 합니다. 확장 유클리드 알고리즘을 사용하면 다음을 만족하는 베주 계수 $n_1, n_2$를 구할 수 있습니다.

$$n_1 m_1 + n_2 m_2 = 1.$$

사실 $n_1$과 $n_2$는 각각 $m_2$와 $m_1$을 법으로 하는 $m_1$과 $m_2$의 모듈러 역원일 뿐입니다. $n_1 m_1 \equiv 1 \pmod{m_2}$이므로 $n_1 \equiv m_1^{-1} \pmod{m_2}$이고, 반대로 $n_2 \equiv m_2^{-1} \pmod{m_1}$입니다.

이 두 계수를 이용하여 해를 다음과 같이 정의할 수 있습니다.

$$a = a_1 n_2 m_2 + a_2 n_1 m_1 \bmod{m_1 m_2}$$

$a \bmod{m_1}$과 $a \bmod{m_2}$를 계산해 보면 이것이 실제로 해임을 쉽게 확인할 수 있습니다.

$$ \begin{array}{rcll} a & \equiv & a_1 n_2 m_2 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 (1 - n_1 m_1) + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 - a_1 n_1 m_1 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 & \pmod{m_1} \end{array} $$

중국인의 나머지 정리는 $m_1 m_2$를 법으로 하는 해가 단 1개만 존재한다는 것도 보장한다는 점에 주목하십시오. 이 또한 쉽게 증명할 수 있습니다.

서로 다른 두 해 $x$와 $y$가 있다고 가정합시다. $x \equiv a_i \pmod{m_i}$이고 $y \equiv a_i \pmod{m_i}$이므로 $x − y \equiv 0 \pmod{m_i}$가 성립하고, 따라서 $x − y \equiv 0 \pmod{m_1 m_2}$, 즉 $x \equiv y \pmod{m_1 m_2}$입니다. 그러므로 $x$와 $y$는 사실 같은 해입니다.

일반적인 경우의 해법¶

귀납적 해법¶

$m_1 m_2$는 $m_3$과 서로소이므로, 법이 몇 개이든 두 개의 법에 대한 해법을 귀납적으로 반복 적용할 수 있습니다. 먼저 처음 두 합동식을 이용하여 $b_2 := a \pmod{m_1 m_2}$를 계산하고, 그다음 합동식 $a \equiv b_2 \pmod{m_1 m_2}$와 $a \equiv a_3 \pmod {m_3}$을 이용하여 $b_3 := a \pmod{m_1 m_2 m_3}$을 계산하는 식으로 진행하면 됩니다.

직접 구성¶

Lagrange 보간법과 유사한 방식으로 해를 직접 구성할 수도 있습니다.

$M_i := \prod_{j \neq i} m_j$를 $m_i$를 제외한 모든 법의 곱이라 하고, $N_i$를 모듈러 역원 $N_i := M_i^{-1} \bmod{m_i}$라 합시다. 그러면 연립 합동식의 해는 다음과 같습니다.

$$a \equiv \sum_{i=1}^k a_i M_i N_i \pmod{m_1 m_2 \cdots m_k}$$

모든 $i$에 대해 $a \bmod{m_i}$를 계산하여 이것이 실제로 해임을 확인할 수 있습니다. $i \neq j$일 때 $M_j$는 $m_i$의 배수이므로 다음이 성립합니다.

$$\begin{array}{rcll} a & \equiv & \sum_{j=1}^k a_j M_j N_j & \pmod{m_i} \\ & \equiv & a_i M_i N_i & \pmod{m_i} \\ & \equiv & a_i M_i M_i^{-1} & \pmod{m_i} \\ & \equiv & a_i & \pmod{m_i} \end{array}$$

구현¶

struct Congruence {
    long long a, m;
};

long long chinese_remainder_theorem(vector<Congruence> const& congruences) {
    long long M = 1;
    for (auto const& congruence : congruences) {
        M *= congruence.m;
    }

    long long solution = 0;
    for (auto const& congruence : congruences) {
        long long a_i = congruence.a;
        long long M_i = M / congruence.m;
        long long N_i = mod_inv(M_i, congruence.m);
        solution = (solution + a_i * M_i % M * N_i) % M;
    }
    return solution;
}

법이 서로소가 아닌 경우의 해법¶

앞서 언급했듯이, 위의 알고리즘은 법 $m_1, m_2, \dots m_k$가 서로소일 때만 동작합니다.

서로소가 아닌 경우, 연립 합동식은 $\text{lcm}(m_1, m_2, \dots, m_k)$를 법으로 정확히 하나의 해를 가지거나 해를 전혀 가지지 않습니다.

예를 들어 다음 연립에서 첫 번째 합동식은 해가 홀수임을 의미하고, 두 번째 합동식은 해가 짝수임을 의미합니다. 어떤 수가 홀수이면서 동시에 짝수일 수는 없으므로, 분명히 해가 존재하지 않습니다.

$$\left\{\begin{align} a & \equiv 1 \pmod{4} \\ a & \equiv 2 \pmod{6} \end{align}\right.$$

연립이 해를 가지는지 판별하는 것은 꽤 간단합니다. 그리고 해가 존재한다면, 원래의 알고리즘을 사용하여 약간 수정된 연립 합동식을 풀 수 있습니다.

하나의 합동식 $a \equiv a_i \pmod{m_i}$는 연립 합동식 $a \equiv a_i \pmod{p_j^{n_j}}$와 동치입니다. 여기서 $p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$는 $m_i$의 소인수분해입니다.

이 사실을 이용하면 연립 합동식을 법이 모두 소수 거듭제곱인 연립 합동식으로 바꿀 수 있습니다. 예를 들어, 위의 연립 합동식은 다음과 동치입니다.

$$\left\{\begin{array}{ll} a \equiv 1 & \pmod{4} \\ a \equiv 2 \equiv 0 & \pmod{2} \\ a \equiv 2 & \pmod{3} \end{array}\right.$$

원래 일부 법이 공통 인수를 가지고 있었으므로, 같은 소수에 기반하지만 소수 거듭제곱은 서로 다를 수 있는 법을 가진 합동식들이 생깁니다.

같은 소수에 기반한 모든 합동식 중에서 가장 높은 소수 거듭제곱을 법으로 가지는 합동식이 가장 강한 합동식임을 관찰할 수 있습니다. 이 합동식은 다른 어떤 합동식과 모순을 일으키거나, 이미 다른 모든 합동식을 함의합니다.

우리의 경우, 첫 번째 합동식 $a \equiv 1 \pmod{4}$는 $a \equiv 1 \pmod{2}$를 함의하므로, 두 번째 합동식 $a \equiv 0 \pmod{2}$와 모순됩니다. 따라서 이 연립 합동식은 해가 없습니다.

모순이 없다면, 이 연립방정식은 해를 가집니다. 가장 높은 소수 거듭제곱을 법으로 가지는 합동식들을 제외한 모든 합동식은 무시할 수 있습니다. 이제 이 법들은 서로소이므로, 앞 절들에서 다룬 알고리즘으로 이 연립을 풀 수 있습니다.

예를 들어 다음 연립은 $\text{lcm}(10, 12) = 60$을 법으로 하는 해를 가집니다.

$$\left\{\begin{align} a & \equiv 3 \pmod{10} \\ a & \equiv 5 \pmod{12} \end{align}\right.$$

이 연립 합동식은 다음 연립 합동식과 동치입니다.

$$\left\{\begin{align} a & \equiv 3 \equiv 1 \pmod{2} \\ a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$

같은 소수를 법으로 가지는 합동식은 $a \equiv 1 \pmod{4}$와 $a \equiv 1 \pmod{2}$뿐입니다. 첫 번째 합동식이 이미 두 번째 합동식을 함의하므로 두 번째 합동식은 무시하고, 대신 서로소인 법을 가지는 다음 연립을 풀면 됩니다.

$$\left\{\begin{align} a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$

이 연립의 해는 $53 \pmod{60}$이며, 실제로 $53 \bmod{10} = 3$이고 $53 \bmod{12} = 5$입니다.

Garner 알고리즘¶

CRT의 또 다른 결과로, 작은 정수들의 배열을 사용하여 큰 수를 표현할 수 있습니다.

비용이 클 수 있는 매우 큰 수로 많은 계산을 하는 대신(1000자리 수로 나눗셈을 한다고 생각해 보십시오), 서로소인 법 몇 개를 골라 큰 수를 연립 합동식으로 표현하고 모든 연산을 연립방정식 위에서 수행할 수 있습니다. $m_1 m_2 \cdots m_k$보다 작은 임의의 수 $a$는 배열 $a_1, \ldots, a_k$로 나타낼 수 있으며, 여기서 $a \equiv a_i \pmod{m_i}$입니다.

위 알고리즘을 사용하면 필요할 때마다 큰 수를 다시 복원할 수 있습니다.

또는 수를 혼합 기수 표현으로 나타낼 수도 있습니다:

$$a = x_1 + x_2 m_1 + x_3 m_1 m_2 + \ldots + x_k m_1 \cdots m_{k-1} \text{ with }x_i \in [0, m_i)$$

별도의 글 Garner 알고리즘에서 다루는 Garner 알고리즘은 계수 $x_i$를 계산합니다. 그리고 이 계수들로 원래의 수 전체를 복원할 수 있습니다.