ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [정수론] 합동식3. 중국인의 나머지 정리
    Math/Number Theory 2023. 8. 3. 22:02

    이전 글에서 합동식 $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$임을 알 수 있다.

     

     

     

     

    'Math > Number Theory' 카테고리의 다른 글

    [정수론] 합동식2. 선형 합동식  (0) 2023.07.06
    [정수론] 합동식1. 합동식의 정의  (0) 2023.07.04

    댓글

Designed by Tistory.