math ps

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

Posted by junk's Blog on February 17, 2023

중국인의 나머지 정리 - CRT

정의

$m_1,m_2,\cdots,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)\\ \vdots\\ x\equiv a_n\ (mod\ m_n)\]

은 법 $m_1,m_2,\cdots,m_n$에 대해 유일한 해를 가진다.

증명

먼저 해의 존재성에 대해서 증명해보자.

$m=m_1m_2\cdots m_k,\ n_k=\cfrac{m}{m_k}$라고 하자. 이때, $\gcd(n_k,m_k)=1$이므로 베주 항등식 $s_kn_k+t_km_k=1$을 만족시키는 $s_k,t_k$가 존재한다. 이를 합동식의 형태로 고치면 $s_kn_k\equiv 1\ (mod\ m_k)$가 된다.

이때, $x=a_1n_1s_1+a_2n_2s_2+\cdots+a_nn_ns_n\ (mod\ m)$라고 하자. $j\neq k$일때 $m_k\vert\ n_j$임은 자명하고, 이에 의해 $x\equiv a_kn_ks_k\equiv a_k\ (mod\ m_k)$이다. 즉, $x$는 연립합동식의 해가 된다.

자, 그러면 유일성에 대해서 증명해보자.

만약 $x,y$가 연립합동식의 해라고 해보자. 그러면

\[x\equiv a_1\ (mod\ m_1)\quad y\equiv a_1\ (mod\ m_1)\\ x\equiv a_2\ (mod\ m_2)\quad y\equiv a_2\ (mod\ m_2)\\ \vdots\\ x\equiv a_n\ (mod\ m_n)\quad y\equiv a_n\ (mod\ m_n)\\\]

이 성립한다. 이때 임의의 $k$에 대해 $x\equiv a_k\equiv y\ (mod\ m_k)$이고, $x-y\equiv0\ (mod\ m_k)$이다.

즉, $x-y$는 모든 $m_k$들의 배수이므로

\[lcm(m_1,m_2,\cdots,m_n)|\ (x-y)\]

이고, 이때 $m$들이 쌍마다 서로소이므로 다음이 성립한다.

\[m_1m_2\cdots m_k|(x-y)\]

즉, $x\equiv y\ (mod\ m_1m_2\cdots m_n)$이고, 연립합동식의 해가 유일함은 증명되었다.

\[x=a_1n_1s_1+\cdots+a_ns_nm_n\]

Coprime?

만약, $m$들이 서로소가 아닌 경우애는 어떻게 해야할까?

이 경우에도 해는 충분히 존재 할 수 있다.

\[x\equiv a_1\ (mod\ m_1)\\ x\equiv a_2\ (mod\ m_2)\]

이때, $x=m_1k_1+a_1$이라 할 수 있고, 두 번째 식에 대입하면 $m_1k_1\equiv a_2-a_1\ (mod\ m_2)$이되고, 정리하면

\[m_1k_1+m_2k_2=a_2-a_1\]

이 된다. 이제 확장 유클리드법으로 $k_1$을 구할 수 있고, 구한 해를 $k_0$이라 하면 정수 $k$에 대해 $k_1=k_0+k\cfrac{m_2}{g}$가 성립한다. 따라서 $x=m_1k_0+k\cfrac{m_1m_2}{g}+a_1$이고, $\cfrac{m_1m_2}{g}=\text{lcm}(m_1,m_2)$이므로

\[x\equiv m_1k_0+a_1\ (mod\ \text{lcm}(m_1,m_2))\]

로 합칠 수 있다.

구현

앞서 과정에서 알아본 것처럼 주어진 $a,m$들에 대해 식들을 확장 유클리드법을 활용하여 차례대로 합쳐나가면 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

typedef long long ll;

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

pair<ll,ll> com(ll a1, ll m1, ll a2, ll m2)
{
    auto [g,k0,_]=eGCD(m1,m2); 
    ll m = m1/g * m2;
    if((a2-a1)%g) return {-1,1};
    ll mul = (a2-a1)/g;
    k0=k0*mul%m2;
    return {(k0*m1+a1)%m,m}
}

pair<ll,ll> crt(vector<ll>&a,vector<ll>&m)
{
    ll ra=a[0], rm=m[0]; 
    for(int i=1;i<m.size();i++)
    {
        auto [a,m]=com(ra,rm,a[i],m[i]);
        if(!~m) return {-1,1};
        else tie(ra,rm)=tie(a,m);
    }
    return {ra,rm};
}

참고 문헌

CATALOG
    FEATURED TAGS
    math ps