3. 중국인의 나머지 정리

관련 코드는 github에서 찾아볼 수 있다.

이 주제도 이미 좋은 자료가 있습니다. https://casterian.net/archives/609

사실 3단원까지만 잘 이해해도 CP/PS 하는데는 문제가 없습니다. 레드까지는 문제 없을듯 ㅋㅋ 

소개가 늦었지만, 앞서 다룬 $ax \equiv b \pmod{c}$와 같이 mod 연산을 다루는 방정식을 합동식이라 한다.

중국인의 나머지 정리는 자연수 $a_1, n_1, a_2, n_2, \cdots , a_k , n_k$가 주어졌을 때, 연립합동식 $$ x \equiv a_i \pmod{n_i} \quad i = 1, 2, \cdots k $$를 푸는 알고리즘이다. 우리의 첫 목표는 $k=2$인 경우를 푸는 것이다. 나중에 가면 알겠지만, $k=2$만 풀면 끝이다.

$x \equiv a_1 \pmod{n_1}$, $x \equiv a_2 \pmod{n_2}$가 성립한다고 가정하자. 정의상, $x = n_1 y + a_1$인 정수 $y$가 있다.

그러니 우리는 $n_1y + a_1 \equiv a_2 \pmod{n_2}$, 또는 $n_1 y \equiv a_2 - a_1 \pmod{n_2}$를 풀면 된다.

그런데 이러한 형태의 합동식은 이미 푸는 방법을 알고 있다. 바로 앞에서 배웠기 때문.

• $g = \text{gcd}(n_1, n_2)$라 하자. 만약 $a_2-a_1$이 $g$의 배수가 아니라면 해는 존재하지 않는다.
• 만약 $a_1 \equiv a_2 \pmod{g}$라면, 앞선 결과에서 우리는 $y \equiv t \pmod{n_2/g}$ 형태의 결과를 얻는다.
• 이는 다른 말로, 적당한 자연수 $m$이 있어서 $y = (n_2/g) m  + t$이라는 것이다.
• $x = n_1y + a_1$에 그대로 대입하면, $x = (n_1n_2/g) m + (n_1t+ a_1)$이다. 즉, $x \equiv (n_1t+ a_1) \pmod{n_1n_2/g}$.
• 여기서 $n_1n_2 / g$가 $\text{lcm}(n_1, n_2)$임을 확인하자. $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$라는 결과 때문.

결국 $k=2$일 때의 결론은, 연립합동식이 해가 없거나 아니면 $x \equiv \text{something} \pmod{\text{lcm}(n_1, n_2)}$라는 결론을 얻는다는 것이다.

이는 연립합동식의 해가 존재하는 경우, 두 합동식을 하나의 합동식으로 합칠 수 있다는 의미가 된다.

• Example. $x \equiv 17 \pmod{42}$, $x \equiv 23 \pmod{60}$을 풀어보자.
• $x \equiv 17 \pmod{42}$에서, $x = 42m + 17$이라고 쓸 수 있다. 
• 이제 $42m + 17 \equiv 23 \pmod{60}$을 풀자. 이는 $42m \equiv 6 \pmod{60}$을 푸는 것과 같다.
• 앞에서 배운 방식을 생각하면, $42m+60n = 6$을 풀면 된다. $\text{gcd}(42, 60) = 6$이므로, $6$으로 식을 나누자.
• $7m+10n = 1$을 풀자. 이는 확장 유클리드 알고리즘으로 가능하며, $m=3$, $n=-2$를 얻는다.
• 여기서 우리는 $m \equiv 3 \pmod{10}$을 얻는다. $m=10t+3$이라 쓰고, $x=42m+17$에 대입하자.
• 그러면 $x = 42(10t+3)+17 = 420t + 143$을 얻고, 이는 $x \equiv 143 \pmod{420}$을 의미한다. 

이제 $k \ge 3$인 경우도 간단하게 해결할 수 있다. 두 합동식을 하나의 합동식으로 합치는 것을 반복하기만 하면 된다.

만약 중간 과정에서 "해가 없다"라는 결론이 나온다면, 전체 연립합동식 역시 해가 없다는 것을 바로 파악할 수 있다.

중국인의 나머지 정리, Chinese Remainder Theorem을 줄여서 CRT로 많이 부른다. 

중국인의 나머지 정리의 심화/응용 내용으로 Garner's Algorithm이 있다. CRT로 큰 수를 다루는 방법이다. 관심이 있다면 링크 참조.