[Algorithm] 정수론 - 중국인의 나머지 정리

정의

중국인의 나머지 정리(The

Chinese Remainder Theorem, CRT)는 여러 개의 서로 다른 소수인 모듈러(moduli)에 대해 독립적으로 주어진 나머지들을 만족하는 정수를 찾는 문제를 해결하는 수학적 정리입니다. 이 정리는 시스템의 일련의 동시 합동식(congruences)을 하나의 합동식으로 표현할 수 있게 해 줍니다. 

중국인의 나머지 정리는 서로 다른 모듈러 \( m_1, m_2, \ldots, m_n \)가 서로 소일 때 (즉, \( \gcd(m_i, m_j) = 1 \) 일 때, \( i \neq j \)) 아래와 같은 연립 합동식에 대하여 해를 찾는 정리입니다

• \( x \equiv a_1 \mod m_1 \)
• \( x \equiv a_2 \mod m_2 \)
• \( x \equiv a_3 \mod m_3 \)
• \( \vdots \)
• \( x \equiv a_n \mod m_n \)

이 연립 합동식은 \( m_1 m_2 \cdots m_n \)을 모듈러로 하여 유일한 해를 갖습니다. 이는 모듈러가 서로 소인 경우에만 적용됩니다.

---

구현 방식

중국인의 나머지 정리의 구현은 주로 '확장 유클리드 알고리즘'을 사용하여 각 합동식의 해를 구하고, 이 해들을 결합하여 원래 문제의 해를 구하는 방식으로 진행됩니다.

• 각 합동식에 대해, 모든 다른 모듈러의 곱을 구합니다.
• 확장 유클리드 알고리즘을 사용하여 각 합동식의 해를 구합니다.
• 이 해들을 결합하여 최종 해를 찾습니다.

한 가지 예를 들어 설명하겠습니다. 아래 3개의 합동식이 주어졌다고 가정하겠습니다.

$$ x \equiv 2 \mod 3 $$

$$ x \equiv 3 \mod 5 $$

$$ x \equiv 2 \mod 7 $$

이 문제는 \( x \)가 3으로 나누었을 때 2의 나머지를, 5로 나누었을 때 3의 나머지를, 그리고 7로 나누었을 때 2의 나머지를 가지는 정수 \( x \)를 찾는 것입니다.

주어진 합동식

 $$ x \equiv 2 \mod 3 ,  x \equiv 3 \mod 5,  x \equiv 2 \mod 7 $$

모듈러의 곱

$$ M = 3 \times 5 \times 7 = 105 $$

각 모듈러에 대한 \( M_i \) 계산

$$ M_1 = \frac{105}{3} = 35 $$
$$ M_2 = \frac{105}{5} = 21 $$
$$ M_3 = \frac{105}{7} = 15 $$

확장 유클리드 알고리즘을 사용하여 \( y_1, y_2, y_3 \)를 각각 구합니다. 이 값들은 각 \( M_i \)가 해당 모듈러에 대하여 역원을 갖는데 사용됩니다.

각 합동식의 해를 계산하여 이들을 합한 후, 모듈러의 곱 \( M \)으로 나눈 나머지를 구합니다. 이러한 방식으로 구해진 값이 주어진 모든 합동식을 만족하는 \( x \)의 값이 됩니다.

#include <iostream>

// 확장 유클리드 알고리즘을 사용하여 x, y를 찾는 함수
int extendedEuclidean(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1;
    int gcd = extendedEuclidean(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

// 중국인의 나머지 정리를 적용하는 함수
int chineseRemainderTheorem(int num[], int rem[], int k) {
    int prod = 1;
    for (int i = 0; i < k; i++)
        prod *= num[i];

    int result = 0;

    for (int i = 0; i < k; i++) {
        int pp = prod / num[i];
        int x, y;
        extendedEuclidean(pp, num[i], x, y);
        result += rem[i] * x * pp;
    }

    return result % prod;
}

int main() {
    int num[] = {3, 5, 7}; // 모듈러
    int rem[] = {2, 3, 2}; // 나머지
    int k = sizeof(num) / sizeof(num[0]);

    std::cout << "x = " << chineseRemainderTheorem(num, rem, k) << std::endl;
    // 출력 결과 : x = 23
    return 0;
}