티스토리 뷰

중국인의 나머지 정리는 PS를 하면서 간혹 등장한다. 답이 큰 경우 일반적으로 $M$으로 나눈 나머지를 출력하라고 한다. 하지만 이 $M$이 고정되어 있지 않고, 입력으로 $k$가지가 주어진다고 할 경우 $k$ 개 경우에 대해서 매번 다 계산하면 오래걸린다. 이럴 때 필요한 것이 바로 중국인의 나머지 정리다.


정리)

서로소인 $k$개의 자연수 $n_1, n_2, \dots, n_k$와 임의의 정수 $a_1, a_2, \dots, a_k$가 있을 때, 임의의 $i (1 \leq i \leq k)$에 대해 $x \equiv a_i (\mod n_i)$ 로 표현되는 변수 $x$의 연립 합동 방정식에 대해, 이 방정식이 성립하는 해 $x = a$가 항상 존재하며, $n_1 n_2 \dots n_k$ 모듈로 안에서 유일하다. 즉, 이 방정식의 해는 $x \equiv a (\mod n_1 n_2 \dots n_k)$로 표현 가능하다.


증명과 계산 방법)

$N = n_1 n_2 \dots n_k$ 라고 하자. $N / n_i$는 $n_i$와 서로소이기 때문에, $r_i n_i + s_i(N / n_i) = 1$인 정수 $r_i, s_i$가 항상 존재한다. (확장 유클리드) 여기에서, $e_i = s_i(N / n_i)$라고 하면 아래와 같은 등식이 성립한다.


$e_i \equiv 1 (\mod n_i)$

$e_i \equiv 0 (\mod n_j) (i \not= j)$


여기에서 $a = \sum\limits^{k}_{i=1}{a_i e_i}$라고 하면, 임의의 $i$에 대해 $a \equiv a_i (\mod n_i)$가 성립한다. 즉, $a$는 우리가 구하고자 하는 해 중 하나이다.


이제 $a$의 $N$ 모듈로 안에서 유일성을 증명하기 위해, 두 해 $x, y$가 존재한다고 가정하자. 그러면 $x \equiv a_i, y \equiv a_i (\mod n_i)$ 이므로 $x - y$는 모든 $n_i$의 배수이고, 따라서 $N$의 배수이다. 즉, $x \equiv y (\mod N)$이므로 해가 유일하다는 것이 증명된다.


확장 유클리드 알고리즘은 모듈로 안에서 곱셈에 대한 역원을 구할 때나, 앞에서 설명한 중국인의 나머지 정리에서 해를 구할 때 사용된다.


이에 대해 간략하게 설명하면 임의의 정수 $a, b$에 대하여 $\gcd(a,b) = ax + by$을 만족하는 $x, y$가 항상 존재한다는 것이다. 이 때, $x$와 $y$를 구할 수 있다.


곱셈의 역원)

$M$ 모듈로 안에서 $n$의 곱셈에 대한 역원이란, $ns \equiv 1 (\mod M)$을 만족하는 $s$를 의미하며, $n$과 $M$이 서로소일 때 존재한다. 확장 유클리드 알고리즘에서의 식에 $n, M, s$를 대입하면 $\gcd(n,M) = xM + ns$ 를 만족하는 $x, s$가 존재하며, $\gcd(n,M) = 1$일 때 $s$는 $M$ 모듈로 안에서 $n$의 곱셈에 대한 역원이 된다.


구하는 방법)


'공부' 카테고리의 다른 글

Suffix Array와 LCP  (12) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (5) 2014.07.25
포함-배제의 원리  (0) 2014.07.20
Nim game  (1) 2013.07.29
댓글
댓글쓰기 폼