52. Chinese Remainder Theorem

정수론에서 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 서로소인 $n$개의 양의 정수 $m_1, m_2, \ldots, m_n$과 $0 \le a_i < m_i$ $(1 \le i \le n)$를 만족하는 $n$개의 정수 $a_1, a_2, \ldots a_n$에 대해 다음 $n$개의 합동식

$$x \equiv a_i \pmod{m_i} \quad (1 \le i \le n)$$

을 모두 만족하는 $0$ 이상 $\prod_{i = 1}^n m_i$ 미만의 정수 $x$가 유일하게 존재한다는 정리이다. 이 정리의 역사는 $5$세기로 거슬러 올라간다. 중국 남북조 시대의 수학서인 『손자산경』에는 다음과 같은 문제가 등장하는데, 이것이 중국인의 나머지 정리가 처음으로 등장하는 자료인 것으로 알려져 있다.

今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問物幾何？
(개수를 알지 못하는 것들이 있다. 셋씩 세면 두 개가 남고, 다섯씩 세면 세 개가 남고, 일곱씩 세면 두 개가 남는다. 총 몇 개인가?)

계산해 보면 개수가 $105k + 23$일 때 답이 될 수 있음을 알 수 있다. 식으로 나타내 보면

$$x \equiv 2 \pmod{3}$$

$$x \equiv 3 \pmod{5}$$

$$x \equiv 2 \pmod{7}$$

이 세 합동식을 모두 만족하는 $0$ 이상 $3 \times 5 \times 7$ 미만의 $x$가 유일하게 존재한다는 뜻이 된다. 이 문제에서는 $x = 23$이 세 합동식을 모두 만족하는 유일한 해이므로 위의 정리에 부합한다.

---

그렇다면 이걸 어떻게 증명하는지 알아보자. 일반적으로 알려진 증명은 두 단계로 이루어져 있는데 첫 번째 단계는 해의 존재성을 보이는 것이다. 먼저 $p_i = \frac{\prod_{j = 1}^n m_j}{m_i}$이라고 하자. 즉 $p_i$는 $m_1$부터 $m_n$ 중 $m_i$를 제외한 모든 값을 곱한 것과 같다. $m_i$가 전부 서로소이므로 $\gcd(m_i, p_i) = 1$일 것이다. 여기에 베주 항등식(Bézout's Identity)을 적용하면

$$P_ip_i + M_im_i = 1$$

을 만족하는 정수 $M_i$와 $P_i$가 존재함을 알 수 있다. 이것을 합동식의 형태로 고치면

$$P_ip_i \equiv 1 \pmod{m_i}$$

이 된다. 이제 $w = \sum_{i = 1}^n a_iP_ip_i$이라고 하자. 이때 $i \ne j$인 경우 $P_i$가 $m_j$의 배수이므로

$$w \equiv a_iP_ip_i \pmod{m_i}$$

가 성립한다. 또한 $P_ip_i \equiv 1 \pmod{m_i}$이므로

$$w \equiv a_i \pmod{m_i}$$

이다. 이것은 $1$ 이상 $n$ 이하인 모든 $i$에 대해 성립하므로 $w$는 주어진 연립 합동식의 해 중 하나이다.

 

두 번째 단계는 해의 유일성을 보이는 것이다. 이쪽은 첫 번째 단계보다 쉬운데, $w_1$과 $w_2$가 주어진 연립 합동식의 해라고 하자. 그렇다면

$$w_1 \equiv a_i \pmod{m_i},\quad w_2 \equiv a_i \pmod{m_i}$$

가 성립한다. 따라서

$$w_1 \equiv w_2 \pmod{m_i}$$

인데 $m_i$가 전부 서로소이므로

$$w_1 \equiv w_2 \pmod{\prod_{i = 1}^n m_i}$$

이다. 이는 주어진 연립 합동식을 만족하는 $0$ 이상 $\prod_{i = 1}^n m_i$ 미만의 해가 유일함을 의미한다.

---

이제 증명을 끝냈으므로 유일한 해를 어떻게 찾는지 알아보자. 사실 위에서 해의 존재성을 보일 때 사용한 방법을 그대로 가져다 쓰면 되긴 하다. 즉 위에 나온 $w$를 구하면 되는데, 앞에서 추가적인 변수 정의가 있었으므로 조금 풀어서 살펴보기로 한다. 먼저

$$w = \sum_{i = 1}^n a_iP_ip_i$$

이고, $P_ip_i \equiv 1 \pmod{m_i}$이지만 무심코 $P_i \equiv p_i^{-1} \pmod{m_i}$을 적용하면 식이 $w = \sum_{i = 1}^n a_i$으로 바뀌는 결과를 초래하므로 $P_i$를 $p_i$의 거듭제곱 꼴로 나타낼 때는 지수를 정확하게 표기해야 한다. $\gcd(p_i, m_i) = 1$이므로 오일러 토션트 함수의 성질에 의해

$$p_i^{\phi(m_i)} \equiv 1 \pmod{m_i}$$

이고, 이 식을 이용하면

$$P_i \equiv p_i^{\phi(m_i) - 1} \pmod{m_i}$$

이 된다. 따라서

$$P_ip_i \equiv p_i^{\phi(m_i)} \pmod{m_i}$$

이다. 그리고 $p_i$를 $m_i$에 대한 식으로 나타내면

$$P_ip_i \equiv (\frac{\prod_{j = 1}^n m_j}{m_i})^{\phi(m_i)} \pmod{m_i}$$

이다. 따라서

$$w = \sum_{i = 1}^n (a_i \times (\frac{\prod_{j = 1}^n m_j}{m_i})^{\phi(m_i)})\,\bmod\, (\prod_{j = 1}^n m_j)$$

이런 식을 유도할 수 있다. 하지만 아직 구현하기에는 살짝 번거로운 형태이므로 구현하기 더 편하게 변형해 보자. 변형 방법은 간단하다. $n$개의 합동식을 한 번에 처리하는 대신 두 개씩 처리하기를 $n - 1$번 반복하는 것이다. 그러면 두 개의 합동식을 푸는 코드만 작성하면 된다. 먼저 위 식에서 $n$에 $2$를 대입하면

$$w = \sum_{i = 1}^2 (a_i \times (\frac{\prod_{j = 1}^2 m_j}{m_i})^{\phi(m_i)})\,\bmod\, (\prod_{j = 1}^2 m_j)$$

$$= \sum_{i =1}^2 (a_i \times (\frac{m_1m_2}{m_i})^{\phi(m_i)})\,\bmod\, (m_1m_2)$$

$$= (a_1 \times (\frac{m_1m_2}{m_1})^{\phi(m_1)} + a_2 \times (\frac{m_1m_2}{m_2})^{\phi(m_2)})\,\bmod\, (m_1m_2)$$

$$= (a_1m_2^{\phi(m_1)} + a_2m_1^{\phi(m_2)})\,\bmod\, (m_1m_2)$$

이제 구현이 훨씬 간단해졌다. 추가로 호출하는 함수가 있긴 하지만 crt 함수 자체는 다음과 같이 한 줄로 끝난다. pow와 phi 함수의 정의는 링크를 참고하면 된다.

int crt(int a1, int m1, int a2, int m2)
{
    return (a1 * pow(m2, phi(m1)) + a2 * pow(m1, phi(m2))) % (m1 * m2);
}

문제는 phi 함수의 시간복잡도가 꽤 느리다는 것이다. 링크에 나온 구현처럼 제곱근 시간에 소인수분해를 하면 $m_i$가 크거나 함수 호출 횟수가 많은 상황에서 사용하기에 적합하지 않고, 그렇다고 폴라드 로를 쓰는 건 배보다 배꼽이 더 큰 상황을 자초하는 것과 같다. 여기서 사용할 수 있는 것이 확장 유클리드 호제법이다. 앞에 $P_ip_i + M_im_i = 1$이라는 식이 있었는데 $n = 2$인 경우 $p_1 = m_2, p_2 = m_1$이므로

$$P_1m_2 + M_1m_1 = 1$$

$$P_2m_1 + M_2m_2 = 1$$

이 되고, $\gcd(m_1, m_2) = 1$이므로 확장 유클리드 호제법을 이용하면 $P_1$과 $P_2$를 구할 수 있다. 여기서 두 번째 식은 $M_2 = P_1, P_2 = M_1$으로 치환했을 때 첫 번째 식과 같아지므로 사실 필요 없는 식이고, 첫 번째 식에서 $P_1$과 $M_1$만 구한 다음 $P_2$ 대신 $M_1$을 쓸 수 있다. 그리고

$$w \equiv a_1P_1p_1 + a_2P_2p_2 = a_1P_1m_2 + a_2P_2m_1 \pmod{m_1m_2}$$

이므로 phi 함수 없이 빠르게 $w$를 구할 수 있게 된다.

구현은 다음과 같다. egcd 함수의 정의는 링크를 참고하면 된다.

int crt(int a1, int m1, int a2, int m2)
{
    pair<int, int> pp = egcd(m1, m2);
    int p1 = pp.second, p2 = pp.first;
    return (a1 * p1 * m2 + a2 * p2 * m1) % (m1 * m2);
}

물론 답이 int 범위에서 나오는 문제들은 그냥 브루트포스로 다 확인해 봐도 빠르게 답을 찾을 수 있는 경우가 많으므로 실제로 이 함수를 쓸 경우 자료형을 다 $8$바이트 정수로 바꿔야 할 가능성이 높다.

---

마지막으로 $m_i$가 서로소가 아닐 수도 있는 경우 중국인의 나머지 정리를 어떻게 활용하는지 알아보자. 두 개의 합동식을 $n - 1$번 처리하는 건 같으므로 $n = 2$이고 $m_1$과 $m_2$가 서로소가 아닌 경우를 살펴보면 된다. $\gcd(m_1, m_2) = g$라고 하자.

 

먼저 $a_1 \equiv a_2 \pmod{g}$를 만족해야 두 합동식의 해가 존재한다. 그렇지 않은 경우 $a_1 \,\bmod\, g \ne a_2 \,\bmod\, g$라는 결과가 나오므로 해가 존재하지 않음을 쉽게 알 수 있다. $a_1 \equiv a_2 \pmod{g}$인 경우,

$$w - (a_1 \,\bmod\, g) \equiv a_1 - (a_1 \,\bmod\, g) \pmod{m_1}$$

$$w - (a_2 \,\bmod\, g) \equiv a_2 - (a_2 \,\bmod\, g) \pmod{m_2}$$

여기서 식의 양변을 $g$로 나눌 수 있다.

$$\frac{w - (a_1 \,\bmod\, g)}{g} \equiv \frac{a_1 - (a_1 \,\bmod\, g)}{g} \pmod{\frac{m_1}{g}}$$

$$\frac{w - (a_2 \,\bmod\, g)}{g} \equiv \frac{a_2 - (a_2 \,\bmod\, g)}{g} \pmod{\frac{m_2}{g}}$$

식을 조금 더 간단하게 표기하면

$$\lfloor \frac{w}{g} \rfloor \equiv \lfloor \frac{a_1}{g} \rfloor \pmod{\frac{m_1}{g}}$$

$$\lfloor \frac{w}{g} \rfloor \equiv \lfloor \frac{a_2}{g} \rfloor \pmod{\frac{m_2}{g}}$$

이때 $\gcd(\frac{m_1}{g}, \frac{m_2}{g}) = 1$이므로 이 두 합동식을 만족하는 해 $\lfloor \frac{w}{g} \rfloor$를 중국인의 나머지 정리로 구할 수 있다. 또한

$$w = g \times \lfloor \frac{w}{g} \rfloor + (a_1 \,\bmod\, g)$$

이므로 처음 합동식의 해도 구할 수 있게 된다. 구현은 다음과 같다.

int crt(int a1, int m1, int a2, int m2)
{
    int g = __gcd(m1, m2);
    if(a1 % g != a2 % g)return -1; // 해가 없는 경우
    pair<int, int> pp = egcd(m1 / g, m2 / g);
    int p1 = pp.second, p2 = pp.first;
    int x = ((a1 / g) * p1 * (m2 / g) + (a2 / g) * p2 * (m1 / g)) % (m1 * m2 / g);
    return g * x + a1 % g;
}

$\frac{w}{g}$를 $x$라는 변수에 저장한다. $7$행에 생략해도 결과가 변하지 않는 괄호가 많이 들어갔는데 가독성을 위한 것이므로 그 괄호들은 편의에 따라 생략해도 무방하다.

 

[참고 링크]

 

Chinese Remainder Theorem

블로그

 

[연습문제]

 

BOJ 1571. 단어 굴리기 (Platinum V)

(Todo)

 

CF 1500B. Two chandeliers (2200)

중국인의 나머지 정리를 이용하여 두 샹들리에에 모두 등장하는 색이 $\operatorname{lcm}(n, m)$일 중 며칠째에 동시에 보이는지를 구한 다음 이분 탐색이나 적절한 처리로 서로 다른 색이 $k$번째로 보이는 날을 구할 수 있다.

 

→ solved.ac tag: crt