나무 숲

수학/ 중국인의 나머지정리 Chinese remainder theorem 본문

Career/알고리즘 · 자료구조

수학/ 중국인의 나머지정리 Chinese remainder theorem

wood.forest 2017. 5. 6. 13:13

중국인의 나머지정리

Chinese remainder theorem



수론과 환론에서, 중국인의 나머지 정리(中國人-定理, 영어: Chinese remainder theorem)는 쌍마다 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 쌍마다 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다.













역사


이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같은 연립 합동 방정식에 관한 문제이다.



今有物,不知其數。三三數之,賸二;五五數之,賸三;七七數之,賸二。問:物幾何?

개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?


答曰:二十三。

정답: 23개.


術曰:三三數之,賸二,置一百四十;五五數之,賸三,置六十三;七七數之,賸二 ,置三十。并之,得二百三十三,以二百一十減之,即得。凡三三數之,賸一,則置七十;五五數之,賸一,則置二十一;七七數之,賸一,則置十五。一百六以上,以一百五減之,即得。

풀이: 셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다.


즉, 이는


x = 2(mod3) = 3(mod5) = 2(mod7)


로 표현된다.

이 경우 풀이에 따라


x = 23( mod 3*5*7 = 210)


이다. 풀이에서 사용된 수는 


140 = 2(mod3) = 0(mod5) = 0(mod7)

63 = 0(mod3) = 3(mod5) = 0(mod7)

30 = 0(mod3) = 0(mod5) = 2(mod7)


이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.


이후 이러한 연립 합동 방정식의 문제의 해법은 1247년 남송의 수학자 진구소(秦九韶)가 저술한 《수서구장》(數書九章)에서 더 일반화되었다.











예제



http://youtoometoo.blogspot.kr/2013/12/chinese-remainder-theorem-crt.html


찾아보다가 위 부분에서 굉장히 보기 쉽게 설명해주신 것 같아 링크를 첨부합니다.

예제 및 계산방법입니다.

















증명


양의 정수 m1, m2..., mr이 쌍마다 서로소이고 m = m1, m2...., mr일 때 임의의 정수 c에 대해

연립일차합동식

x = c(mod m1)

x = c(mod m2)

...

x = c(mod mr)

은 유일한 해 x = c(mod m)을 가진다.


증명은 크게 존재성, 유일성 두 가지로 나뉜다. 또한 이 정리를 증명하기에 앞서 도움정리를 알아두어야 한다.



도움정리

양의 정수 m과 a_1,a_2,\cdots,a_n에 대하여 m이 a_1,a_2,\cdots,a_n와 각각 서로소이면, m과 a_1a_2\cdots a_n은 서로소이다.

a_1a_2\cdots a_n 공약수인 소수 p가 존재한다. p\mid a_1a_2\cdots a_n이므로 p\mid a_i a_i가 존재한다. 그러면 p a_i m을 모두 나누고, 이는 가정에 모순이다.



양의 정수 m a_1,a_2,\cdots,a_n에 대하여 m a_1,a_2,\cdots,a_n의 각각의 배수이면 m \text{lcm}\left(a_1,a_2,\cdots,a_n\right)의 배수이다.

나눗셈 정리에 의하여 m=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r 을 만족하는 정수 q,r이 유일하게 존재한다 (0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right)). 그런데 a_i m \text{lcm}\left(a_1,a_2,\cdots,a_n\right)을 모두 나누므로 a_i r도 나눠야 한다. 이것은 모든 i에 대해 참이므로 r \text{lcm}\left(a_1,a_2,\cdots,a_n\right)보다 작은 a_i들의 공배수이다. 이것을 만족하는 값은 r=0밖에 없으며, 이는 곧 m \text{lcm}\left(a_1,a_2,\cdots,a_n\right)의 배수임을 보인다.


양의 정수 a_1,a_2,\cdots,a_n에 대하여 \gcd\left(a_i,a_j\right)=1,i\neq j(즉, 쌍마다 서로 소(pairwise relatively prime))이면, 이 성립한다.

최소공배수 증명을 통해 알 수 있다.





존재성

라고 하자. 또, n_k=\frac{m}{m_k}라고 놓자. 즉, n_k는 m_k를 제외한 나머지 m_i들의 곱을 의미한다.
도움정리 1로부터 \gcd\left(n_k,m_k\right)=1이다. 그럼 베주 항등식에 의해, 
s_k n_k + t_k m_k =1
을 만족하는 정수 s_k,t_k가 존재한다. 이를 합동식 형태로 고치면,
s_k n_k\equiv1\left(\text{mod}\,m_k\right)
이다. 이제
x = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n
라고 놓자. j\neq k이면 m_k\mid n_j이고,[4] 따라서
x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\text{mod}\,m_k\right)이다.(1<=k<=n인 임의의 자연수)[5][6]
즉, x는 주어진 연립 합동식의 한 해이다.






유일성

가 주어진 연립 합동식의 해라고 하자.[7]그러면,
x\equiv a_1\left(\text{mod}\,m_1\right)y\equiv a_1\left(\text{mod}\,m_1\right)
x\equiv a_2\left(\text{mod}\,m_2\right)y\equiv a_2\left(\text{mod}\,m_2\right)
\vdots
x\equiv a_n\left(\text{mod}\,m_n\right)y\equiv a_n\left(\text{mod}\,m_n\right)
이다. 그러므로, 임의의 k\,\left(1\leq k\leq n\right)에 대하여, x\equiv a_k\equiv y\left(\text{mod}\,m_k\right)이고, 그래서 x-y\equiv0\left(\text{mod}\,m_k\right)이다.[8] 즉, x-y는 모든 m_k들의 배수이다. 따라서 도움정리 2에 의해,
\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)
이다. 그런데, m_1,m_2,\cdots,m_n들이 쌍마다 서로 소이므로, 도움정리 3으로부터
m_1 m_2 \cdots m_n\mid\left(x-y\right)이다. 즉,
x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right)이고, 이는 주어진 연립 합동식의 해가 유일함을 보인다.






대수적 증명

은 쌍마다 서로소이므로 유한생성아벨군의 기본정리에 의해 \mathbb{Z_{m_1m_2\cdots m_n}}은 \mathbb{Z_{m_1}} \times \mathbb{Z_{m_2}} \times \mathbb{\cdots} \times \mathbb{Z_{m_n}}과 isomorphic하다. 따라서 \mathbb{Z_{m_1m_2\cdots m_n}}에서의 해는 \mathbb{Z_{m_1}} \times \mathbb{Z_{m_2}} \times \mathbb{\cdots} \times \mathbb{Z_{m_n}}에서의 해와 유일하게 대응된다.





-

https://ko.wikipedia.org/wiki/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%A0%95%EB%A6%AC

https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC

728x90
반응형
Comments