-
[정수론] 합동식3. 중국인의 나머지 정리Math/Number Theory 2023. 8. 3. 22:02
이전 글에서 합동식 ax≡bmodn을 푸는 방법을 알아보았다.
우선, 해가 존재할 조건은 바로 d=gcd(a,n)에 대해 d∣b인 것이다.
또, x0이 위의 합동식의 한 해일 때 x=x0+(n/d)t (단, t=0,1,...,d−1)가 다른 해임을 알아보았다.
이번 글에서는 여러개의 연립 합동식을 푸는 방법을 알아볼 것이다.
연립 합동식
이제, 다음과 같은 서로 다른 r개의 합동식을 생각해보자.
a1x≡b1modm1
a2x≡b2modm2
...
arx≡brmodmr
이 연립 합동식을 풀어볼 것이다.
그 전에 우선, 두 가지 가정을 먼저 해볼 것이다.
당연하게도 각각의 합동식은 해가 존재해야 하므로 dk=gcd(ak,mk)에 대해 dk∣bk이다.
또한, 모든 mk은 쌍마다 서로소이다.
결과적으로, k번째 합동식의 양변을 dk로 나누어 정리하면, 연립 합동식의 해는 아래의 조건을 만족할 것이다.
x≡c1modn1
x≡c2modn2
...
x≡crmodnr
단, nk=mk/dk이다.
즉, 우리는 연립 합동식을 위와 같이 간단한 형태로 치환할 수 있음을 알 수 있다.
결국 어떠한 연립 합동식을 풀기 위해서는 위의 형태의 연립 합동식을 풀면 된다는 것이다.
그리고 이러한 형태의 연립 합동식을 푸는 방법을 바로 중국인의 나머지 정리라고 한다.
중국인의 나머지 정리
Theorem. 정수 m1,m2,...,mn이 쌍마다 서로소일 때, 다음 n개의 합동식은 법 (m1×m2×...×mn)에 대해 유일한 해를 갖는다.
x≡a1modm1
x≡a2modm2
...
x≡armodmn
중국인의 나머지 정리는 해의 유일성과 존재성을 보일 수 있는 강력한 도구이다.
이제 증명을 해보자.
증명이 상당히 길고 도움 정리가 필요하지만, 정수론에서 매우 중요한 정리이므로 천천히 증명해보도록 하겠다.
Proof 1. 해의 존재성 - 위의 연립 합동식은 해를 갖는다.
우선 위의 연립 합동식을 만족하는 정수 x가 존재함을 증명해보자.
그 전의 다음 보조 정리를 먼저 증명해야 한다.
Lemma 1. 양의 정수 m과 a1,a2,...,ar에 대하여 m과 모든 ak가 서로소라면 m과 a1a2...ar은 서로소이다.
이 보조 정리는 귀류법을 이용해서 간단하게 증명할 수 있다. 즉, 서로소가 아니라고 가정해보자.
그러면 정수 m과 a1a2...ar의 공약수인 소수 p가 존재할 것이다.
즉, p∣m이며 p∣a1a2...ar이다.
이때 만약 모든 ak에 대해 p∤ak라면 p∤a1a2...ar이다.
따라서 p∣ak인 ak가 존재해야 한다.
결과적으로 소수 p는 m과 어떤 ak의 공약수이므로 이는 m과 모든 ak가 서로소라는 가정에 모순이다.
이제 lemma 1을 이용하여 연립 합동식의 해의 존재 여부를 증명해보자.
m=m1m2...mn으로 두자. 그리고 m′k=m/mk라고 두자.
(즉, m′k=m1m2...mk−1mk+1...mn이다.)
Lemma 1에 의해, mk와 m′k은 서로소이다.
그럼 디오판토스 방정식 xkm′k+ykmk=1의 해가 존재한다.
즉, xkm′k−1=−ykmk 이므로, yk∣xkm′k−1이다.
따라서 합동식 xkm′k≡1modmk가 성립한다.
이제 x=a1m′1x1+a2m′2x2+...+anm′nxn라고 하자.
그럼 x≡a1m′1x1+a2m′2x2+...+anm′nxn≡akm′kxkmodmk가 성립한다.
이때 xkm′k≡1modmk 이므로, x≡akmodmk가 모든 1≤k≤n에 대해 성립한다.
따라서 x는 연립 합동식의 해이다. ◼
Proof 2. 해의 유일성 - 위의 연립 합동식은 유일한 해를 갖는다.
위의 연립 합동식이 서로 다른 두 해를 갖는다고 가정한 후, 두 해가 사실 서로 같음을 보일 것이다.
이를 위해서 다음의 보조 정리를 우선 증명할 것이다.
Lemma 2. 양의 정수 m과 a1,a2,...,ar에 대해, 모든 ak에 대해 ak∣m 이라면 a1,a2,...,ar의 최소공배수를 A라 할 때 A∣m이다.
m=Aq+r(0≤r<A)을 만족하는 정수 q와 r은 유일하게 존재한다.
그런데 모든 ak에 대해 ak∣m인 동시에 ak∣A이므로 ak∣r이 성립한다.
따라서 r은 모든 a1,a2,...,ar의 공배수이다.
그런데 0≤r<A 이므로 r=0일 수밖에 없다. 결과적으로 m=Aq이므로 A∣m이다.
이제 연립 합동식의 해의 유일성을 증명해보겠다.
우선 x,y가 모두 연립 합동식의 해라고 가정하자.
즉, 다음이 성립한다.
x≡y≡a1modm1
x≡y≡a2modm2
...
x≡y≡anmodmn
즉, 모든 1≤k≤n에 대하여 x−y≡0modmk가 성립한다.
따라서 x−y는 모든 mk의 배수이다.
이때 모든 mk의 최소공배수를 M이라고 하면 lemma 2에 의해, M∣x−y이다.
그런데 m1,m2,...,mn은 쌍마다 서로소이므로 M=m1m2...mn임을 알 수 있다.
따라서 M∣x−y 이면 m1m2...mn∣x−y인 것이다.
결과적으로 x≡ymodm1m2...mn이므로, 법 m1m2...mn에 대해 x와 y가 합동이다.
따라서 법 m1m2...mn에 대해 연립 합동식은 유일한 해를 갖는다. ◼
실제로 해를 구하는 방법
우리는 쌍마다 서로소인 정수 m1,m2,...,mn에 대해 연립 합동식
x≡a1modm1
x≡a2modm2
...
x≡armodmn
은 무조건 유일하게 해를 갖는다는 사실을 알 수 있었다.
이 연립 합동식의 실제 해를 구하는 방법은 다음과 같다.
우선, m′k=m1m2...mk−1mk+1...mn으로 두자.
그리고 k개의 합동식 m′kx≡1modmk를 풀어 해 xk를 각각 구하자.
그러면 x=a1m′1x1+a2m′2x2+...+anm′nxn는 연립 합동식의 해가 된다.
연습문제
이제 실제로 문제를 풀어보자.
다음 세 개의 합동식을 동시에 만족시키는 정수 x의 값을 구하자.
x≡2mod3
x≡3mod5
x≡2mod7
우선 m′1=5×7=35, m′2=3×7=21, m′3=3×5=15로 두자.
그리고 다음 세 개의 합동식을 각각 풀어보자.
35x≡1mod3,21x≡1mod5,15x≡1mod7
이때 x1=2,x2=1,x3=1임을 쉽게 구할 수 있다.
따라서 최종 해는 x=2×35×2+3×21×1+2×15×1=233임을 알 수 있다.
'Math > Number Theory' 카테고리의 다른 글
[정수론] 합동식2. 선형 합동식 0 2023.07.06 [정수론] 합동식1. 합동식의 정의 0 2023.07.04