중국인의 나머지 정리 설명(Chinese Remainder Therem, CRT)

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

2020.04.23 코드가 잘못된 것을 확인했습니다. 앳코더 라이브러리판 crt는 맞는데 제 꺼는 틀렸습니다. 확인하고 수정하겠습니다.

2020.04.27 제가 착각했습니다. 틀린 줄 알았는데 제가 코드를 옮길 때 정확히 옮기지 않았네요. 블로그 상에 올라와 있는 코드는 전부 int인데 long long으로 옮기다가 잘못 옮겼습니다. 포스트의 코드도 long long 버전으로 바꾸겠습니다.

$$
\begin{aligned}
x \equiv &a_1 \; (mod \; m_1) \\
x \equiv &a_2 \; (mod \; m_2) \\
&\vdots \\
x \equiv &a_k \; (mod \; m_k)
\end{aligned}
$$

위와 같이 하나의 변수 $x$에 대하여 여러개의 합동식이 있을 때, 어떤 수 $N$에 대하여 위 식을 모두 만족하는 $0 \le x \lt N$를 찾아주는 것이 중국인의 나머지 정리이다.

좀더 어렵게 말하면 선형 연립 합동식을 풀어주고, 그 해인 $x$는 모든 법의 최소공배수를 $L=LCM(m_1,m_2,...,m_k)$이라고 했을 때, $0 \le x \lt L$을 만족하는 $x$를 찾을 수 있다는 것이다. 위에서 말한 어떤 수 $N$은 사실 모든 법 $m_i$들의 최소공배수였다.

여기서 $m_i, m_j$끼리 서로소가 아니어도 구할 수 있다. 이 정리는 $k$개의 합동식이 있을 때, 해를 찾아줄 수 있다. 먼저, 식 2개만 있을 때, 해를 어떻게 구하는지 본 다음 그걸 $k$개로 확장하자.

$$
\begin{aligned}
x \equiv &a_1 \; (mod \; m_1) \\
x \equiv &a_2 \; (mod \; m_2) \\
\end{aligned}
$$

이런 합동식 두개가 있다고 하자. $m_1$과 $m_2$의 최대공약수를 $g=GCD(m_1,m_2)$라고 하자. 그러면 다음을 만족해야 함을 알 수 있다.

$$
\begin{aligned}
x-a_1 &\equiv 0 \; (mod \; g) \\
x-a_2 &\equiv 0 \; (mod \; g) \\
a_1 &\equiv a_2 \; (mod \; g)
\end{aligned}
$$

만약 $a_1, a_2$가 이를 만족하지 못한다면, 해는 없는 것이다. 따라서 위 조건을 만족한다고 생각하고 $x$를 구하자.

$$
m_1 p + m_2 q = g
$$

베주 항등식에 의해서 위 식이 정수해 $(p,q)$를 갖는 것은 알 수 있고, $m_1,m_2$의 최대공약수가 $g$이기 때문에 양변을 $g$로 나눌수 있다.

$$
\frac{m_1}{g}p + \frac{m_2}{g}q = 1
$$

확장 유클리드 알고리즘을 이용하면 $(p,q)$를 계산하는 것은 가능하다. 그렇게 $(p,q)$를 계산하고 나면 $x$를 다음과 같이 정할 수 있다.

$$
x = a_1\frac{m_2}{g}q + a_2\frac{m_1}{g}p
$$

이 $x$가 원래의 합동식을 만족하는지 보자. $\frac{m_1}{g}p + \frac{m_2}{g}q = 1$ 을 만족하기 때문에 $\frac{m_1}{g}p = 1 - \frac{m_2}{g}q$이다. 이를 대입하자.

$$
\begin{aligned}
x &= a_1\frac{m_2}{g}q + a_2(1-\frac{m_2}{g}q) \\
&= a_2 + (a_1 - a_2)\frac{m_2}{g}q
\end{aligned}
$$

여기서 기억해야할 사실은 $a_1 \equiv a_2 \; (mod \; g)$라는 것이다. 이 합동식의 우변을 좌변으로 넘기면 $a_1-a_2 \equiv 0 \; (mod \; g)$이다. 즉, $a_1-a_2$가 $g$로 나누어 떨어진다는 사실이다. 그래서 $\frac{a_1-a_2}{g}$는 정수이기 때문에 위 식을 다시 쓰면

$$
\begin{aligned}
x &= a_2 + \frac{a_1-a_2}{g}qm_2 \\
x &\equiv a_2 \; (mod \; m_2)
\end{aligned}
$$

$x$가 $m_2$에 대한 합동식을 만족하는 것을 볼 수 있다. $m_1$에 대해서 $x$가 합동식을 만족하는 것을 보이는 것은 베주 항등식에서 $m_1$의 항을 우변으로 넘기고 대입하면 같은 방식으로 보일 수 있다.

이제 두 합동식을 만족하는 하나의 $x$를 찾은 것이다. 기억해야 할 것이 우린 $0 \le x \lt LCM(m_1,m_2)$인 $x$를 찾고자 하는 것이 목표였다. 이를 위해서는 그냥 $x$에 $LCM(m_1, m_2)$로 나눈 나머지를 취하면 된다. 이를 다시 쓰면 아래와 같다.

$$
\begin{aligned}
x &\equiv a_1 \; (mod \; m_1) \\
x &\equiv a_2 \; (mod \; m_2) \\
x &\equiv a_1\frac{m_2}{g}q + a_2\frac{m_1}{g}p \; (mod \; LCM(m_1,m_2))
\end{aligned}
$$

위 식들을 잘 보면 첫 두 식에 대한 해로 $x$를 구했더니 이 $x$에 대한 합동식이 하나 나온 것이라고 봐도 된다. 즉, 두 개의 합동식을 하나로 줄였다!

그럼 이런 합동식이 $k$개가 있다 하면, 이러한 단계를 총 $k-1$번 반복하면 합동식이 하나만 남게 되고, 그 때의 합동식의 결과는 우리가 원하는 $x$가 된다.

정리하자. 우리는 아래와 같은 합동식 두 개를 가지고 있다고 하자.

$$
\begin{aligned}
x \equiv &a_1 \; (mod \; m_1) \\
x \equiv &a_2 \; (mod \; m_2) \\
\end{aligned}
$$

그러면 이 합동식은 $a_1 \equiv a_2 \; (mod \; GCD(m_1,m_2))$일 때, 다음과 같은 합동식 하나로 줄일 수 있다.

$$
x \equiv a_1\frac{m_2}{g}q + a_2\frac{m_1}{g}p \; (mod \; LCM(m_1,m_2))
$$

기억해두자. 저 조건을 만족 못하면 해는 없다. 이러한 단계를 반복해나가면서 $k$개의 합동식을 줄여나간다면 최종적으로는 모든 합동식을 만족하는 $0 \le x \lt LCM(m_1,m_2,...m_k)$를 찾을 수 있다.

아래는 실제로 해인 $x$를 구해주는 중국인의 나머지 정리 코드이다. 여기서는 모든 자료형을 int로 맞춰놓긴 했지만 일반적으로는 int범위를 넘어가는 경우가 매우 많으니 실제로 코드를 쓸 땐 자료형에 주의해서 수정할 필요가 있다.

코드에서 A는 $a_1, a_2, ... , a_k$를 가지고 있는 벡터고, M은 $m_1, m_2, ... , m_k$를 가지고 있는 벡터이다.

2020.04.23 코드가 잘못된 것을 확인했습니다. 앳코더 라이브러리판 crt는 맞는데 제 꺼는 틀렸습니다. 확인하고 수정하겠습니다.

2020.04.27 제가 착각했습니다. 틀린 줄 알았는데 제가 코드를 옮길 때 정확히 옮기지 않았네요. 블로그 상에 올라와 있는 코드는 전부 int인데 long long으로 옮기다가 잘못 옮겼습니다. 포스트의 코드도 long long 버전으로 바꾸겠습니다.

// gcd(a,b), s,t where a*s + b*t = gcd(a,b)
pair<ll,pair<ll,ll>> xGCD(ll a, ll b) {
    if(b == 0) return {a,{1,0}};
    pair<ll,pair<ll,ll>> ret = xGCD(b, a%b);
    ll g, x, y;
    g = ret.first;
    tie(x,y) = ret.second;
    return {g,{y,x-(a/b)*y}};   
}

// A = [a_1, a_2, ... , a_N]
// M = [m_1, m_2, ... , m_N]
// each equation is x = a_i (mod m_i)
// it returns {-1,-1} if there's no solution satisfying N linear congruence equations.
pair<ll,ll> CRT(vector<ll> &A, vector<ll> &M) {
    if(A.size() != M.size()) return {-1,-1};
    int N = A.size();
    ll a1 = A[0];
    ll m1 = M[0];
    a1 %= m1;
    for(int i=1;i<N;++i) {
        ll a2 = A[i];
        ll m2 = M[i];
        ll g = __gcd(m1, m2);
        if(a1 % g != a2 % g) return {-1,-1};
        ll p, q;
        auto res = xGCD(m1/g, m2/g);
        tie(p,q) = res.second;
        i128 mod = (i128)m1 / g * m2;
        a1 = ((i128)a1 * (m2/g) % mod) * q % mod + ((i128)a2*(m1/g)%mod)*p % mod;
        a1 = (a1 + mod) % mod;
        m1 = mod;
    }
    return {a1, m1};
}

Reference

https://forthright48.com/chinese-remainder-theorem-part-1-coprime-moduli/

https://forthright48.com/chinese-remainder-theorem-part-2-non-coprime-moduli/