[정수론] 합동식3. 중국인의 나머지 정리

이전 글에서 합동식 $ax \equiv b \bmod n$을 푸는 방법을 알아보았다.

 

우선, 해가 존재할 조건은 바로 $d = \mathrm{gcd}(a, n)$에 대해 $d \mid b$인 것이다. 

또, $x_0$이 위의 합동식의 한 해일 때 $x = x_0 + (n/d)t$ $($단, $t = 0, 1, ..., d-1$$)$가 다른 해임을 알아보았다. 

 

 

이번 글에서는 여러개의 연립 합동식을 푸는 방법을 알아볼 것이다. 

 

 

연립 합동식

 

이제, 다음과 같은 서로 다른 $r$개의 합동식을 생각해보자. 

 

 

$$a_1x \equiv b_1 \bmod m_1$$

$$a_2x \equiv b_2 \bmod m_2$$

$$...$$

$$a_rx \equiv b_r \bmod m_r$$

 

 

이 연립 합동식을 풀어볼 것이다. 

그 전에 우선, 두 가지 가정을 먼저 해볼 것이다.

 

당연하게도 각각의 합동식은 해가 존재해야 하므로 $d_k = \mathrm{gcd}(a_k, m_k)$에 대해 $d_k \mid b_k$이다.

또한, 모든 $m_k$은 쌍마다 서로소이다. 

 

결과적으로, $k$번째 합동식의 양변을 $d_k$로 나누어 정리하면, 연립 합동식의 해는 아래의 조건을 만족할 것이다.

 

$$x \equiv c_1 \bmod n_1$$

$$x \equiv c_2 \bmod n_2$$

$$...$$

$$x \equiv c_r \bmod n_r$$

 

단, $n_k = m_k / d_k$이다. 

 

즉, 우리는 연립 합동식을 위와 같이 간단한 형태로 치환할 수 있음을 알 수 있다.

결국 어떠한 연립 합동식을 풀기 위해서는 위의 형태의 연립 합동식을 풀면 된다는 것이다. 

 

그리고 이러한 형태의 연립 합동식을 푸는 방법을 바로 중국인의 나머지 정리라고 한다.

 

 

 

---

 

 

 

중국인의 나머지 정리

 

Theorem. 정수 $m_1, m_2, ... , m_n$이 쌍마다 서로소일 때, 다음 $n$개의 합동식은 법 $(m_1 \times m_2 \times ... \times m_n)$에 대해 유일한 해를 갖는다.

$$x \equiv a_1 \bmod m_1$$

$$x \equiv a_2 \bmod m_2$$

$$...$$

$$x \equiv a_r \bmod m_n$$

 

 

 

중국인의 나머지 정리는 해의 유일성과 존재성을 보일 수 있는 강력한 도구이다.

이제 증명을 해보자. 

 

증명이 상당히 길고 도움 정리가 필요하지만, 정수론에서 매우 중요한 정리이므로 천천히 증명해보도록 하겠다. 

 

 

 

Proof 1. 해의 존재성 - 위의 연립 합동식은 해를 갖는다.

 

우선 위의 연립 합동식을 만족하는 정수 $x$가 존재함을 증명해보자.

그 전의 다음 보조 정리를 먼저 증명해야 한다.

 

 

Lemma 1. 양의 정수 $m$과 $a_1, a_2, ... , a_r$에 대하여 $m$과 모든 $a_k$가 서로소라면 $m$과 $a_{1}a_{2} ... a_{r}$은 서로소이다.

 

이 보조 정리는 귀류법을 이용해서 간단하게 증명할 수 있다. 즉, 서로소가 아니라고 가정해보자. 

그러면 정수 $m$과 $a_{1}a_{2} ... a_{r}$의 공약수인 소수 $p$가 존재할 것이다. 

 

즉, $p \mid m$이며 $p \mid a_{1}a_{2} ... a_{r}$이다. 

이때 만약 모든 $a_k$에 대해 $p \nmid a_k$라면 $p \nmid a_{1}a_{2} ... a_{r}$이다.

따라서 $p \mid a_k$인 $a_k$가 존재해야 한다.

 

 

결과적으로 소수 $p$는 $m$과 어떤 $a_k$의 공약수이므로 이는 $m$과 모든 $a_k$가 서로소라는 가정에 모순이다. 

 

 

---

 

이제 lemma 1을 이용하여 연립 합동식의 해의 존재 여부를 증명해보자.

 

$m = m_1m_2 ... m_n$으로 두자. 그리고 $m_k' = m / m_k$라고 두자. 

$($즉, $m_k' = m_1m_2 ... m_{k-1}m_{k+1} ... m_n$이다.$)$

 

Lemma 1에 의해, $m_k$와 $m_k'$은 서로소이다. 

그럼 디오판토스 방정식 $x_km_k' + y_km_k = 1$의 해가 존재한다.

 

즉, $x_km_k' - 1 = - y_km_k$ 이므로, $y_k \mid x_km_k' - 1$이다. 

따라서 합동식 $x_km_k' \equiv 1 \bmod m_k$가 성립한다.

 

 

이제 $x = a_1m_1'x_1 + a_2m_2'x_2 + ... + a_nm_n'x_n$라고 하자.

그럼 $x \equiv a_1m_1'x_1 + a_2m_2'x_2 + ... + a_nm_n'x_n \equiv a_km_k'x_k \bmod m_k$가 성립한다.

이때 $x_km_k' \equiv 1 \bmod m_k$ 이므로, $x \equiv a_k \bmod m_k$가 모든 $1 \leq k \leq n$에 대해 성립한다.

 

따라서 $x$는 연립 합동식의 해이다. $\blacksquare$

 

 

 

 

 

 

 

Proof 2. 해의 유일성 - 위의 연립 합동식은 유일한 해를 갖는다.

 

위의 연립 합동식이 서로 다른 두 해를 갖는다고 가정한 후, 두 해가 사실 서로 같음을 보일 것이다. 

 

이를 위해서 다음의 보조 정리를 우선 증명할 것이다. 

 

 

Lemma 2. 양의 정수 $m$과 $a_1, a_2, ... , a_r$에 대해, 모든 $a_k$에 대해 $a_k \mid m$ 이라면 $a_1, a_2, ... , a_r$의 최소공배수를 $A$라 할 때 $A \mid m$이다.

 

$m = Aq + r (0 \leq r < A)$을 만족하는 정수 $q$와 $r$은 유일하게 존재한다. 

그런데 모든 $a_k$에 대해 $a_k \mid m$인 동시에 $a_k \mid A$이므로 $a_k \mid r$이 성립한다.

 

따라서 $r$은 모든 $a_1, a_2, ... , a_r$의 공배수이다. 

그런데 $0 \leq r < A$ 이므로 $r = 0$일 수밖에 없다. 결과적으로 $m = Aq$이므로 $A \mid m$이다.

 

---

이제 연립 합동식의 해의 유일성을 증명해보겠다.

 

우선 $x, y$가 모두 연립 합동식의 해라고 가정하자.

즉, 다음이 성립한다.

$x \equiv y \equiv a_1 \bmod m_1$

$x \equiv y \equiv a_2 \bmod m_2$

$...$

$x \equiv y \equiv a_n \bmod m_n$

 

즉, 모든 $1 \leq k \leq n$에 대하여 $x-y \equiv 0 \bmod m_k$가 성립한다.

따라서 $x-y$는 모든 $m_k$의 배수이다. 

이때 모든 $m_k$의 최소공배수를 $M$이라고 하면 lemma 2에 의해, $M \mid x-y$이다.

 

그런데 $m_1, m_2, ... , m_n$은 쌍마다 서로소이므로 $M = m_1m_2 ... m_n$임을 알 수 있다.

따라서 $M \mid x-y$ 이면 $m_1m_2 ... m_n \mid x-y$인 것이다. 

 

결과적으로 $x \equiv y \bmod m_1m_2 ... m_n$이므로, 법 $m_1m_2 ... m_n$에 대해 $x$와 $y$가 합동이다.

따라서 법  $m_1m_2 ... m_n$에 대해 연립 합동식은 유일한 해를 갖는다. $\blacksquare$

 

 

 

---

 

 

실제로 해를 구하는 방법

 

 

우리는 쌍마다 서로소인 정수 $m_1, m_2, ... , m_n$에 대해 연립 합동식

 

$$x \equiv a_1 \bmod m_1$$

$$x \equiv a_2 \bmod m_2$$

$$...$$

$$x \equiv a_r \bmod m_n$$

 

은 무조건 유일하게 해를 갖는다는 사실을 알 수 있었다.

이 연립 합동식의 실제 해를 구하는 방법은 다음과 같다.

 

우선, $m_k' = m_1m_2 ... m_{k-1}m_{k+1}...m_n$으로 두자.

그리고 $k$개의 합동식 $m_k'x \equiv 1 \bmod m_k$를 풀어 해 $x_k$를 각각 구하자. 

 

그러면 $x = a_1m_1'x_1 + a_2m_2'x_2 + ... + a_nm_n'x_n$는 연립 합동식의 해가 된다. 

 

 

 

 

 

연습문제

 

 

이제 실제로 문제를 풀어보자. 

 

다음 세 개의 합동식을 동시에 만족시키는 정수 $x$의 값을 구하자.

$$x \equiv 2 \bmod 3$$

$$x \equiv 3 \bmod 5$$

$$x \equiv 2 \bmod 7$$

 

 

우선 $m_1' = 5 \times 7 = 35$, $m_2' = 3 \times 7 = 21$, $m_3' = 3 \times 5 = 15$로 두자.

 

그리고 다음 세 개의 합동식을 각각 풀어보자.

$35x \equiv 1 \bmod 3, 21x \equiv 1 \bmod 5, 15x \equiv 1 \bmod 7$

 

이때 $x_1 = 2, x_2 = 1, x_3 = 1$임을 쉽게 구할 수 있다. 

따라서 최종 해는 $x = 2\times35\times2 + 3\times21\times1 + 2\times15\times1 = 233$임을 알 수 있다.