중국인의 나머지 정리(Chinese remainder theorem)

중국인의 나머지 정리를 이해하기 위해 기초적인 문제를 차근차근 풀어보자.
아래 문제만 풀 수 있다면 한결 가까워질 것이다.

문제

[아이]
할아버지, 나이가 어떻게 되십니까?

[할아버지]
내 나이는 3으로 나누었을 때 1이 남고,
5로 나누었을 때 3이 남고,
7로 나누었을 때 2가 남는단다.

[아이]
;;

풀이과정

할아버지의 말씀 3가지를 수식으로 바꿔보면 다음과 같다.

$x \equiv 1\ (mod\ 3)$
$x \equiv 3\ (mod\ 5)$
$x \equiv 2\ (mod\ 7)$

위 세 개를 만족하는 $x$ 를 구해보자.

우선 첫 번째 수식 $x \equiv 1\ (mod\ 3)$ 만 놓고 보면 간단하다.
$x = 3n + 1$

두 번째 수식 $x \equiv 3\ (mod\ 5)$ 을 풀기 위해 위 $x$ 를 대입하고 변환해보자.
$3n + 1 \equiv 3\ (mod\ 5)$ $\Rightarrow 3n \equiv 2\ (mod\ 5)$

덧셈, 뺄셈, 곱셈은 modular연산에서 닫혀있기 때문에 양 변에 -1을 취해도 식은 성립한다. 하지만 $3n$ 을 풀기 위해 양 변에 나눗셈을 할 수는 없다. 따라서 $n$ 을 구하기 위해서는 양 변에 $Z_5 = \{0, 1, 2, 3, 4\}$ 에서 3에 대한 곱셈의 역원을 구해야 한다.

그럼 잠시 곱셈의 역원을 구하는 방법에 대해 먼저 알아보자.

곱셈의 역원 구하는 방법

1. 전부 해보는 방법 $O(N)$

int modInverse(int a, int m) { 
    for(int i = 1; i < m; i++) {
       if ((a*i) % m == 1) {
          return i; 
       }
    }
}

2. 페르마 소정리 $O(log_2 N)$

$m$ 이 소수, $a$ 가 $m$ 의 배수가 아니라면 $a^{m-1}\equiv 1\ (mod\ m)$
$a \times a^{m-2} \equiv 1\ (mod\ m)$
이전글 참조
제곱의 성질을 이용하면 더 빠르게 가능

int modInverse(int a, int m) {
      int result = 1;
      for(int i = 0; i < m-2; i++) {
        result = (result * a) % m
      }
      return result;
}

3. 확장 유클리드 $O(log_2 N)$

$3n \equiv 1\ (mod\ 5)$
$3n = 5m + 1$
$3n - 5m = 1$ 를 만족하는 n과 m을 구하는 방법

// return: <gcd(a, b), n, m>
tuple<int, int, int> xGCD(int a, int b) {
      if (b == 0) {
          return make_tuple(a, 1, 0);
      }
      int g, x, y;
      tie(g, x, y) = xGCD(b, a%b);
      return make_tuple(g, y, x-(a/b)*y);
}

위와 같이 여러 가지 방법으로 modular 내에서 곱셈의 역원을 구할 수 있다. 그럼 다시 돌아와서 $3n \equiv 2\ (mod\ 5)$ 를 만족하는 $n$ 을 구해보자.

$Z_5 = \{0, 1, 2, 3, 4\}$ 에서 3에 대한 곱셈의 역원을 구하면 2가 나온다. 양 변에 2를 곱하면 좌변을 $n$ 으로 만들 수 있다.
$n \equiv 4\ (mod\ 5)$ $n = 5m + 4$ $\Rightarrow x = 15m + 13$

이제 마지막 세 번째 수식 $x \equiv 2\ (mod\ 7)$ 에 $x$ 를 대입해보자.
$15m + 13 \equiv 2\ (mod\ 7)$ $15m \equiv 3\ (mod\ 7)$

$Z_7 = \{0, 1, 2, 3, 4, 5, 6\}$ 에서 15에 대한 곱셈의 역원은 1!!
$m \equiv 3\ (mod\ 7)$ $m = 7k + 3$ $\Rightarrow x = 105k + 58$

이렇게 알맞은 $x$ 를 구했고, 처음 식에 대입해보면 올바르다는 것을 알 수 있다.

세 번쯤 반복해보니 이 노가다를 수식으로 정리하면 그것이 중국인의 나머지 정리가 된다.