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

중국인의 나머지정리

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))이면, lcm(a​1​​,a​2​​,⋯,a​n​​)=a​1​​a​2​​⋯a​n​​이 성립한다.

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

존재성

m=m​1​​m​2​​⋯m​n​​라고 하자. 또, $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$는 주어진 연립 합동식의 한 해이다.

유일성

$x,y$가 주어진 연립 합동식의 해라고 하자.[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)$이고, 이는 주어진 연립 합동식의 해가 유일함을 보인다.

대수적 증명

m​1​​,m​2​​,⋯,m​n​​은 쌍마다 서로소이므로 유한생성아벨군의 기본정리에 의해 $\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