Processing math: 100%

ABOUT ME

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

    이전 글에서 합동식 axbmodn을 푸는 방법을 알아보았다.

     

    우선, 해가 존재할 조건은 바로 d=gcd(a,n)에 대해 db인 것이다. 

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

     

     

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

     

     

    연립 합동식

     

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

     

     

    a1xb1modm1

    a2xb2modm2

    ...

    arxbrmodmr

     

     

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

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

     

    당연하게도 각각의 합동식은 해가 존재해야 하므로 dk=gcd(ak,mk)에 대해 dkbk이다.

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

     

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

     

    xc1modn1

    xc2modn2

    ...

    xcrmodnr

     

    단, nk=mk/dk이다. 

     

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

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

     

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

     

     

     


     

     

     

    중국인의 나머지 정리

     

    Theorem. 정수 m1,m2,...,mn이 쌍마다 서로소일 때, 다음 n개의 합동식은 법 (m1×m2×...×mn)에 대해 유일한 해를 갖는다.

    xa1modm1

    xa2modm2

    ...

    xarmodmn

     

     

     

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

    이제 증명을 해보자. 

     

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

     

     

     

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

     

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

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

     

     

    Lemma 1. 양의 정수 ma1,a2,...,ar에 대하여 m과 모든 ak가 서로소라면 ma1a2...ar은 서로소이다.

     

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

    그러면 정수 ma1a2...ar의 공약수인 소수 p가 존재할 것이다. 

     

    즉, pm이며 pa1a2...ar이다. 

    이때 만약 모든 ak에 대해 pak라면 pa1a2...ar이다.

    따라서 pakak가 존재해야 한다.

     

     

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

     

     


     

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

     

    m=m1m2...mn으로 두자. 그리고 mk=m/mk라고 두자. 

    (즉, mk=m1m2...mk1mk+1...mn이다.)

     

    Lemma 1에 의해, mkmk은 서로소이다. 

    그럼 디오판토스 방정식 xkmk+ykmk=1의 해가 존재한다.

     

    즉, xkmk1=ykmk 이므로, ykxkmk1이다. 

    따라서 합동식 xkmk1modmk가 성립한다.

     

     

    이제 x=a1m1x1+a2m2x2+...+anmnxn라고 하자.

    그럼 xa1m1x1+a2m2x2+...+anmnxnakmkxkmodmk가 성립한다.

    이때 xkmk1modmk 이므로, xakmodmk가 모든 1kn에 대해 성립한다.

     

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

     

     

     

     

     

     

     

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

     

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

     

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

     

     

    Lemma 2. 양의 정수 ma1,a2,...,ar에 대해, 모든 ak에 대해 akm 이라면 a1,a2,...,ar의 최소공배수를 A라 할 때 Am이다.

     

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

    그런데 모든 ak에 대해 akm인 동시에 akA이므로 akr이 성립한다.

     

    따라서 r은 모든 a1,a2,...,ar의 공배수이다. 

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

     


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

     

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

    즉, 다음이 성립한다.

    xya1modm1

    xya2modm2

    ...

    xyanmodmn

     

    즉, 모든 1kn에 대하여 xy0modmk가 성립한다.

    따라서 xy는 모든 mk의 배수이다. 

    이때 모든 mk의 최소공배수를 M이라고 하면 lemma 2에 의해, Mxy이다.

     

    그런데 m1,m2,...,mn은 쌍마다 서로소이므로 M=m1m2...mn임을 알 수 있다.

    따라서 Mxy 이면 m1m2...mnxy인 것이다. 

     

    결과적으로 xymodm1m2...mn이므로, 법 m1m2...mn에 대해 xy가 합동이다.

    따라서 법  m1m2...mn에 대해 연립 합동식은 유일한 해를 갖는다.

     

     

     


     

     

    실제로 해를 구하는 방법

     

     

    우리는 쌍마다 서로소인 정수 m1,m2,...,mn에 대해 연립 합동식

     

    xa1modm1

    xa2modm2

    ...

    xarmodmn

     

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

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

     

    우선, mk=m1m2...mk1mk+1...mn으로 두자.

    그리고 k개의 합동식 mkx1modmk를 풀어 해 xk를 각각 구하자. 

     

    그러면 x=a1m1x1+a2m2x2+...+anmnxn는 연립 합동식의 해가 된다. 

     

     

     

     

     

    연습문제

     

     

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

     

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

    x2mod3

    x3mod5

    x2mod7

     

     

    우선 m1=5×7=35, m2=3×7=21, m3=3×5=15로 두자.

     

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

    35x1mod3,21x1mod5,15x1mod7

     

    이때 x1=2,x2=1,x3=1임을 쉽게 구할 수 있다. 

    따라서 최종 해는 x=2×35×2+3×21×1+2×15×1=233임을 알 수 있다.

     

     

     

     

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

    댓글

Designed by Tistory.