[include(틀:정수론)] [목차] {{{+2 Chinese Remainder Theorem}}} == 개요 == 중국의 5세기 문헌인 『손자산경(孫子算經)』[* 여기에서의 '손자(孫子)'는 『[[손자병법]]』을 쓴 그 '손자'와 한자는 같지만 그보다 훨씬 후대의 인물이다.][* 중국의 옛 수학서에는 이 『손자산경(孫子算經)』 외에도, 『주비산경(周髀算經)』, 『구장산술(九章算術)』, 『해도산경(海島算經)』, 『오조산경(五曹算經)』, 『하후양산경(夏侯陽算經)』, 『장구건산경(張邱建算經)』, 『오경산술(五經算術)』, 『집고산경(緝古算經)』, 『철술(綴術)』 등이 있다. 이들을 통틀어 '산경십서(算經十書)'로 칭한다.]에는 다음과 같은 문제가 있다고 한다. >3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? [* 풀이는 아래쪽 문단 참조. 답은 23, 128 등등이다.] 이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 '''중국인의 나머지 정리'''가 되었다고 한다. 위 문제는 뭔가 초등학교 문제집에나 나올 법한 느낌이지만[* [[그런데 그것이 실제로 일어났습니다]] 의외로 초등학교 문제집에 이런 문제들이 나오고, 심지어 중학교 방정식 단원에 나오는 경우도 있다.] 실은 '''연립 [[합동식]]''' 문제로, [[정수론]]과 관련된 내용이다. 초등학생들이 못 푸는 게 당연한 것. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다. 아래 정리를 읽기 전에, [[이때는 대략 정신이 멍해진다|정신이 안드로메다로 가는 듯한 느낌(...)]]을 받지 않기 위해선 반드시 [[합동식]] 문서를 읽고 오자. mod에 대해 간단히 설명하자면, [math(A\left(\text{mod}\,B\right))]면 [math(B)]로 나누어 [math(A)]의 나머지를 생기게 하는 수라는 뜻이다. [math(C=A\left(\text{mod}\,B\right))]라면 일반적인 방정식으로는 [math(C=Bk+A)], ([math(0\leq A<B, k\in)]ℤ)로 나타난다. 자세한 정리는 다음과 같다. >[math(m_1,m_2,\cdots,m_n)]이 쌍마다 서로 소(즉, [math(\gcd\left(m_i,m_j\right)=1,i\neq j)])이면, 다음 연립 [[합동식]] >[math(x\equiv a_1\left(\text{mod}\,m_1\right))] >[math(x\equiv a_2\left(\text{mod}\,m_2\right))] >[math(x\equiv a_3\left(\text{mod}\,m_3\right))] >[math(\vdots)] >[math(x\equiv a_n\left(\text{mod}\,m_n\right))] >은 법 [math(m_1 m_2\cdots m_n)]에 대하여 유일한 해를 갖는다. == 증명 == 증명은 크게 존재성, 유일성 두 가지로 나뉜다. 또한 이 정리를 증명하기에 앞서 도움정리를 알아두어야 한다. === 도움정리 1 === >양의 정수 [math(m)]과 [math(a_1,a_2,\cdots,a_n)]에 대하여 [math(m)]이 [math(a_1,a_2,\cdots,a_n)]와 각각 [[서로소]]이면, [math(m)]과 [math(a_1a_2\cdots a_n)]은 서로소이다. 증명 ||서로소가 아니라고 가정하자. 그럼 [math(m)]과 [math(a_1a_2\cdots a_n)]의 [[공약수]]인 소수 [math(p)]가 존재한다. [math(p\mid a_1a_2\cdots a_n)]이므로 [math(p\mid a_i)]인 [math(a_i)]가 존재한다. 그러면 [math(p)]는 [math(a_i)]와 [math(m)]을 모두 나누고, 이는 가정에 모순이다. || === 도움정리 2 === >양의 정수 [math(m)]과 [math(a_1,a_2,\cdots,a_n)]에 대하여 [math(m)]이 [math(a_1,a_2,\cdots,a_n)]의 각각의 [[배수(수학)|배수]]이면 [math(m)]은 [math(\text{lcm}\left(a_1,a_2,\cdots,a_n\right))]의 배수이다. 증명 ||[[나눗셈 정리]]에 의하여 [math(m=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r)] 을 만족하는 정수 [math(q,r)]이 유일하게 존재한다 ([math(0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right))]). 그런데 [math(a_i)]가 [math(m)]과 [math(\text{lcm}\left(a_1,a_2,\cdots,a_n\right))]을 모두 나누므로 [math(a_i)]는 [math(r)]도 나눠야 한다. 이것은 모든 [math(i)]에 대해 참이므로 [math(r)]은 [math(\text{lcm}\left(a_1,a_2,\cdots,a_n\right))]보다 작은 [math(a_i)]들의 [[공배수]]이다. 이걸 만족하는 값은 [math(r=0)]밖에 없으며, 이는 곧 [math(m)]이 [math(\text{lcm}\left(a_1,a_2,\cdots,a_n\right))]의 배수임을 보인다.|| === 도움정리 3 === >양의 정수 [math(a_1,a_2,\cdots,a_n)]에 대하여 [math(\gcd\left(a_i,a_j\right)=1,i\neq j)](즉, '''쌍마다 서로 소'''(pairwise relatively prime))이면, >[math(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)=a_1 a_2 \cdots a_n)]이 성립한다. 이에 대한 증명은 [[최소공배수]] 참조. 사실 증명이라 할 것도 없다. === 존재성 === [math(m=m_1 m_2 \cdots m_n)]라고 하자. 또, [math(n_k=\frac{m}{m_k})]라고 놓자. 즉, [math(n_k)]는 [math(m_k)]를 제외한 나머지 [math(m_i)]들의 곱을 의미한다. 도움정리 1로부터 [math(\gcd\left(n_k,m_k\right)=1)]이다. 그럼 [[베주 항등식]]에 의해, [math(s_k n_k + t_k m_k =1)] 을 만족하는 정수 [math(s_k,t_k)]가 존재한다. 이를 [[합동식]] 형태로 고치면, [math(s_k n_k\equiv1\left(\text{mod}\,m_k\right) )] 이다. 이제 [math(x = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n)] 라고 놓자. [math(j\neq k)]이면 [math(m_k\mid n_j)]이고,[* [math(n_k)]의 정의 때문에 성립] 따라서 [math(x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\text{mod}\,m_k\right) )]이다.(1<=k<=n인 임의의 자연수)[* 나머지 [math(a_j n_j s_j)]는 [math(m_k)]로 나누면 나머지가 0 이므로 [math(j=k)]인 경우만 생각해 주면 된다.][* 또한 [math(n_k s_k)]는 위 [math(s_k n_k\equiv 1\left(\text{mod}\,m_k\right))]와 합동식의 성질 때문에 1로 바뀐다.] 즉, [math(x)]는 주어진 연립 합동식의 한 해이다. === 유일성 === [math(x,y)]가 주어진 연립 합동식의 해라고 하자.[* 임의의 두 답이 같음을 보이는 방법은 유일성을 증명하는 데 자주 쓰이는 테크닉이다.]그러면, [math(x\equiv a_1\left(\text{mod}\,m_1\right))], [math(y\equiv a_1\left(\text{mod}\,m_1\right))] [math(x\equiv a_2\left(\text{mod}\,m_2\right))], [math(y\equiv a_2\left(\text{mod}\,m_2\right))] [math(\vdots)] [math(x\equiv a_n\left(\text{mod}\,m_n\right))], [math(y\equiv a_n\left(\text{mod}\,m_n\right))] 이다. 그러므로, 임의의 [math(k\,\left(1\leq k\leq n\right))]에 대하여, [math(x\equiv a_k\equiv y\left(\text{mod}\,m_k\right))]이고, 그래서 [math(x-y\equiv0\left(\text{mod}\,m_k\right))]이다.[* 추이율. [[합동식]]의 성질 참조] 즉, [math(x-y)]는 모든 [math(m_k)]들의 배수이다. 따라서 도움정리 2에 의해, [math(\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right))] 이다. 그런데, [math(m_1,m_2,\cdots,m_n)]들이 쌍마다 서로 소이므로, 도움정리 3으로부터 [math(m_1 m_2 \cdots m_n\mid\left(x-y\right))]이다. 즉, [math( x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right))]이고, 이는 주어진 연립 합동식의 해가 유일함을 보인다. == 문제를 푸는 방법 == 위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다. 3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 [math(3\times5\times7=105)]에 대하여 유일한 해를 가진다. [math(m=105,n_1=35,n_2=21,n_3=15)]라 하자. [math(n_1 s_1\equiv35s_1\equiv2s_1\equiv1\left(\text{mod}\,3\right))] [math(n_2 s_2\equiv21s_2\equiv s_2\equiv1\left(\text{mod}\,5\right))] [math(n_3s_3\equiv15s_3\equiv s_3\equiv1\left(\text{mod}\,7\right))] 을 풀면 [math(s_1=2,s_2=1,s_3=1)]가 해임을 알 수 있다.[* 여러 값 중 아무거나 고르면 된다.] 그러므로 [math(x \equiv a_1 n_1 s_1 + a_2 n_2 s_2 + a_3n_3s_3 \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \equiv 233 \equiv 23 \left(\text{mod}\,105\right))]이다. 따라서 [math(x\equiv23\left(\text{mod}\,105\right))]가 주어진 연립 합동식의 해이다. == 결론 == 풀어서 말하면 서로소인 [math(n)]개의 수 각각에 대해 일정한 나머지를 만족하는 수는 그들 [math(n)]개의 최소공배수에 일정한 나머지를 더한 값으로 나타난다는 정리이다. 사실 어떤 자연수 [math(A)]에 대해 일정한 나머지 [math(B)]를 가지는 수에 [math(A)]의 배수를 더하면 이 또한 [math(A)]로 나눈 나머지가 [math(B)]이므로, 존재성과 유일성을 증명하고 나면 [math(n)]개 수의 최소공배수마다 조건을 만족하는 수가 반복되어 나타난다는 것은 쉽게 유추가 가능하다. == 관련 문서 == * [[합동식]] * [[최대공약수]] * [[최소공배수]] * [[환(대수학)#s-6.1]] [[분류:정수론]]