중국인의 나머지 정리와 확장 유클리드 알고리즘

1) 중국인의 나머지 정리

중국인의 나머지 정리는 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)$이므로 해가 유일하다는 것이 증명된다.

 

2) 일반적인 상황에서 연립 합동 방정식의 해 구하기

변수 $x$에 대한 연립 합동 방정식이 두 개 있다고 하자.

$$x \equiv a_1 \mod m_1\\x \equiv a_2 \mod m_2$$

이 방정식의 해 $x$가 존재한다면, 다음과 같다. $x = k_1m_1 + a_1 = k_2m_2 + a_2$. 이 식은 다음과 같이 정리할 수 있다.

$$k_1m_1 - k_2m_2 = a_2-a_1$$

$m_1$과 $m_2$의 최대공약수를 $g$라고 하자. 만약 두 수가 서로소라면 $g=1$이다. 위 식을 만족하는 정수 $k_1$과 $k_2$가 존재하기 위한 필요충분조건은 $a_2-a_1$가 $g$의 배수여야 한다. (확장 유클리드 알고리즘)

$k_1$과 $k_2$의 정수해는 여러 쌍이 있을 수 있다. 그중 $k_1$의 임의의 해를 $k_0$라 하자. 확장 유클리드 알고리즘을 통해 $k_0$를 구할 수 있다.

$k_1$의 일반해는 다음과 같이 표현할 수 있다.

$$k_1 = k_0 + l\frac{m_2}{g}$$

즉, $k_1$의 정수해는 $\text{mod} \frac{m_2}{g}$에서 유일하다. 이를 $x = k_1m_1 + a_1$에 대입하면 다음과 같다.

$$x = k_0m_1+l\frac{m_1m_2}{g} + a_1$$

즉, $x$의 해가 $\text{mod} \frac{m_1m_2}{g}$에서 유일하며, 그 해는 다음과 같다.

$$x \equiv k_0m_1 + a_1 \mod \frac{m_1m_2}{g}$$

 

3) 확장 유클리드 알고리즘

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

 

이에 대해 간략하게 설명하면 임의의 정수 $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$의 곱셈에 대한 역원이 된다.

 

구하는 방법)

int ee(int a,int b,int &s,int &t) { if (!b){ s = 1, t = 0; return a; } int q = a/b, r = a%b, sp, tp; int g = ee(b,r,sp,tp); s = tp; t = sp-tp*q; return g; }