중국인의 나머지 정리
덤프버전 :
분류
1. 개요[편집]
중국인의 나머지 정리(Chinese remainder theorem; CRT)[1] 는 남북조시대 중국의 5세기 문헌인 『손자산경(孫子算經)』[2][3] 에는 나오는 문제로, 내용은 다음과 같다.
뭔가 초등학교 문제집에나 나올 법한 느낌이지만[5] 실은 연립 합동식 문제로, 정수론과 관련된 내용이다. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다. 이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.今有物,不知其數。三三數之,賸二;五五數之,賸三;七七數之,賸二。問物幾何?
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 (정)수는 무엇인가?[4]
아래 정리를 읽기 전에, 이해를 쉽게 하기 위해선 반드시 합동식 문서를 읽고 오자. 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(B\mid(C-A))]로 나타낸다.
자세한 정리는 다음과 같다.
단순히 연립합동식을 푸는 것보다는 해가 유일하게 '존재'한다는 엄청난 성질을 갖고 있음에 정말 강력한 도구이다.[6][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)]에 대하여 유일한 해를 갖는다.
2. 증명[편집]
증명은 크게 존재성, 유일성 두 가지로 나뉜다. 또한 이 정리를 증명하기에 앞서 도움정리를 알아두어야 한다.
2.1. 도움정리 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.2. 도움정리 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<\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))]의 배수임을 보인다.
2.3. 도움정리 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)]이 성립한다.
2.4. 존재성[편집]
[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)]이고,[7] 따라서
[math(x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\text{mod}\,m_k\right) )]이다.([math(1\leq k\leq n)]인 임의의 자연수)[8][9]
즉, [math(x)]는 주어진 연립 합동식의 한 해이다.
2.5. 유일성[편집]
[math(x,y)]가 주어진 연립 합동식의 해라고 하자.[10] 그러면,
[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))]이다.[11] 즉, [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. 문제를 푸는 방법[편집]
위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다.
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)]가 해임을 알 수 있다.[12] 그러므로 [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))]가 주어진 연립 합동식의 해이다.
4. 결론[편집]
풀어서 말하면 서로소인 [math(n)]개의 수 각각에 대해 일정한 나머지를 만족하는 수는 그들 [math(n)]개의 최소공배수에 일정한 나머지를 더한 값으로 나타난다는 정리이다. 사실 어떤 자연수 [math(A)]에 대해 일정한 나머지 [math(B)]를 가지는 수에 [math(A)]의 배수를 더하면 이 또한 [math(A)]로 나눈 나머지가 [math(B)]이므로, 존재성과 유일성을 증명하고 나면 [math(n)]개 수의 최소공배수마다 조건을 만족하는 수가 반복되어 나타난다는 것은 쉽게 유추가 가능하다.
5. 대수학적 확장[편집]
환의 용어로 중국인의 나머지 정리를 다음과 같이 일반화할 수 있다.
단위원을 갖는 환 [math(R)]과 그것의 two-side 아이디얼 (two-side ideal) [math(I_{1},\ldots,\, I_{n})]을 생각하자. [math(\left\{I_{i}:i=1,\ldots,\,n\right\})]이 comaximal[13]
하다고 하자. 그러면, [math(R/\left({\displaystyle \bigcap_{i}}I_{i}\right) \cong {\displaystyle \prod_{i}}\left(R/I_{i}\right))]이다. (여기서 [math({\displaystyle \prod_{i}}\left(R/I_{i}\right))]에 componentwise한 환 구조를[14] 주었다.)특히, 임의의 [math(a \in R)]에 대해 [math(a + \bigcap_{i} I_{i} \in R/\left({\displaystyle \bigcap_{i}}I_{i}\right))]을 [math((a + I_1, a + I_2, \cdots, a + I_n) \in {\displaystyle \prod_{i}}\left(R/I_{i}\right))]로 보내는 사상은 잘 정의된 환 동형사상(ring isomorphism)이다.
중국인의 나머지 정리와 전혀 안 똑같아 보이지만, 단계적으로 접근하여 이 모티브를 확인할 수 있다. 이를 위해 [math(R)]이 PID인 경우에 집중해 보자. 이 경우 각 [math(i)]에 대하여 적당한 기약 (irreducible) 원소 [math(p_i)]가 존재해 [math(I_i = (p_i))]이다. 그리고 [math(I_i + I_j = R)]일 필요충분조건은 [math(p_i)]와 [math(p_j)]가 서로소인 것이다. 그리고 다음이 성립한다.
이제 어떤 원소들 [math(a_i)]들에 대하여 다음과 같이 쓸 수 있다.[math(a \equiv b \;\; (\textrm{mod }p_i) \;\;\; \leftrightarrow \;\;\; a + (p_i) = b + (p_i))].
한편 임의의 [math(a_i \in R)]들에 대하여 [math((a_1 + I_1, a_2 + I_2, \cdots, a_n + I_n) \in \prod_i (R/I_i))]가 항상 존재하며, 반대로 당연하지만 [math(\prod_i (R/I_i))]의 모든 원소들이 어떤 [math(a_i \in R)]들에 대하여 [math((a_1 + I_1, a_2 + I_2, \cdots, a_n + I_n))] 꼴로 써진다.모든 [math(i)]에 대하여 [math(a \equiv a_i \;\; (\textrm{mod }p_i))]
[math(\leftrightarrow)] 모든 [math(i)]에 대하여 [math(a + I_i = a_i + I_i)].
이제 다음 질문을 생각해 보자.
[math(R = \Z)]일 때 이 질문에 대한 답이 중국인의 나머지 정리에 의해 주어진다는 것을 알 수 있다. [math(a)]가 유일하지는 않지만 대신에 법 [math(p_1 p_2 \cdots p_n)]에 대해 유일하다는 것은 안다. 그런데 사실 [math(R)]이 PID인 상황에서 두 [math(a, b \in R)]에 대하여 [math(a \equiv b \;\; (\textrm{mod }p_1 p_2 \cdots p_n))]인 필요충분조건은 [math(a + \bigcap_i I_i = b + \bigcap_i I_i)]인 것이다.기약 원소 [math(p_i)]들과 임의의 [math(a_i \in R)]이 주어져 있을 때 모든 [math(i)]에 대하여 [math(a \equiv a_i \;\; (\textrm{mod }p_i))]인 [math(a \in R)]이 존재하는가? 존재한다면 유일한가?
이제 위 질문을 다음과 같이 환의 언어로 번역할 수 있음을 보자.
그리고 중국인의 나머지 정리에 따르면 일단 [math(R = \Z)]인 경우에 한하여 해당 [math(a)]가 존재하며, 만약 어떤 두 답 [math(a, b)]를 찾았다면 [math(a + \bigcap_i I_i = b + \bigcap_i I_i)]임을 알 수 있다.아이디얼 [math(I_i)]들과 임의의 [math((a_1 + I_1, a_2 + I_2, \cdots, a_n + I_n) \in \prod_i (R/I_i))]에 대하여 [math((a + I_1, a + I_2, \cdots, a + I_n) = (a_1 + I_1, a_2 + I_2, \cdots, a_n + I_n))]인 [math(a \in R)]이 존재하는가? 존재한다면 유일한가?
여기서 더 나아가 보자. 다음과 같은 사상을 정의할 수 있다.
[math(\displaystyle \phi: R \to \prod_i (R/I_i))],
[math(\displaystyle \phi(a) = (a + I_1, a + I_2, \cdots, a + I_n))].
[math(\prod_i (R/I_i))]에 componentwise한 환 구조가 부여되어 있을 때 [math(\phi)]가 환 준동형사상(ring homomorphism)임을 쉽게 확인할 수 있다. 그리고 물론 [math(a + \ker \phi = b + \ker \phi)]이면 그리고 그럴 때에만 [math(\phi(a) = \phi(b))]임을 안다. 이제 사상(map)의 언어까지 추가하여 위 문제를 다음과 같이 번역할 수 있음을 보자.
그리고 중국인의 나머지 정리에 따라 일단 [math(R = \Z)]인 경우에 한하여 답이 다음과 같음을, 즉 중국인의 나머지 정리를 환과 사상의 언어로 번역한 결과물이 다음과 같음을 알 수 있다.Comaximal한 아이디얼 [math(I_i)]들이 주어져 있고 위와 같이 환 준동형사상 [math(\phi)]가 정의되어 있을 때, [math(\phi)]는 전사(surjective)인가? 그리고 [math(\ker \phi)]는 무엇인가?[15]
여기에 제1 동형 정리까지 끼얹으면 결국 중국인의 나머지 정리를 최종적으로 다음과 같이 번역할 수 있다.[math(\phi)]는 전사이며 [math(\ker \phi = \bigcap_i I_i)]이다.
정확하게 맨 위에 주어진 것과 똑같은 내용이다. 한편 어느 순간서부턴가 [math(R)]은 PID라는 가정이 아무래도 상관 없어졌음을 알 수 있다. 여기서 이 가정까지 지우는 것으로 중국인의 나머지 정리 최종 일반화를 얻을 수 있다.Comaximal한 아이디얼들 [math(I_i)] ([math(i = 1, 2, \cdots, n)])이 주어져 있고 사상 [math(\tilde{\phi}: R / \left( \bigcap_i I_i \right) \to \prod_i (R/I_i))]가 [math(\tilde{\phi}\left(a + \bigcap_i I_i \right) = (a + I_1, a + I_2, \cdots, a + I_n))]이도록 정의된다면, [math(\tilde{\phi})]는 잘 정의된 환 동형사상(ring isomorphism)이다.
다만 이건 그냥 중국인 나머지 정리에 해당하는 명제를 환과 사상의 언어로 번역하고 일반화한 것에 불과하다. 그리고 그 과정 중에서 사용된 일반화들에 대한 정당화, 그러니까 증명 같은 게 일절 없었음을 보자. 무슨 소리냐면 이걸 증명하는 건 또다른 문제라는 것이다. 다행히 증명은 그리 어렵지 않다. 그리고 다소 복잡해 보이는 최종 버전 말고 그 바로 전 버전, 즉 [math(\phi)]는 전사이며 [math(\ker \phi = \bigcap_i I_i)]임만 보이면 된다. 다시, 제1 동형 정리에 의하여 이걸 보이면 최종 버전이 바로 성립하기 때문이다. 이는 아래 단락에서 설명하도록 하겠다.
이게 무슨 지적유희냐고 할 수 있겠지만, 이러한 일반화를 통해 정수론이 아닌 다른 영역에서도 중국인의 나머지 정리와 비슷한 결과를 얻을 수 있다는 점이 중요하다. 물론 환과 사상의 언어로 번역을 한다는 게 결국 그런 의미이긴 하다. 예를 들어 다음을 얻을 수 있다.[16]
마지막으로 하나 더, 아마 몇몇 사람들은 저 정리에서 가환환이라는 조건이 없다는 것을 눈치챘을 것이다.[17] 실제로 그 조건마저 없애는 (대신에 물론 two-sided ideal들만 생각하는) 일반화까지 가능하다는 것을 아래 증명으로부터 볼 수 있다.서로소인 다항식들 [math(p_i(t))]와 임의의 다항식들 [math(g_i(t))]에 대하여 [math(f(t) \equiv g_i(t) \;\; (\textrm{mod }p_i(t)))]인 다항식 [math(f(t))]가 존재하며, 유일(up to modulo [math(\prod_i p_i(t))])하다.
5.1. 증명[편집]
그 중에서도 쉬운 쪽인 [math(\ker \phi = \bigcap_i I_i)]를 먼저 확인해 보자. 다음 몇 줄로 간단하게 증명된다.
[math(\displaystyle a \in \ker \phi)]
[math(\leftrightarrow)] [math(\displaystyle \phi(a) = (a + I_1, a + I_2, \cdots, a + I_n) = 0)]
[math(\leftrightarrow)] 모든 [math(i)]에 대해 [math(\displaystyle a \in I_i)]
[math(\leftrightarrow)] [math(\displaystyle a \in \bigcap_i I_i)].
이제 [math(\phi)]가 전사임을 보여보자. 다음 두 보조정리를 보인 다음, [math(n)]에 대한 수학적 귀납법으로 전사임을 보이는 쓰는 방식을 쓸 것이다.
[math((I_1 \cap I_2) + J)]이 단위원 1을 가진다는 것을 보이는 것으로 증명을 해 보이도록 하겠다.[18] Comaximal하다는 가정으로부터 다음을 만족하는 [math(a, b \in I_1)], [math(c, d \in I_2)], [math(x, y \in J)]를 찾을 수 있다.(보조정리 1-1) 세 comaximal한 two-sided 아이디얼들 [math(I_1)], [math(I_2)], [math(J)]에 대하여 [math(I_1 \cap I_2)]와 [math(J)] 역시 comaximal하다. 즉, [math((I_1 \cap I_2) + J = R)]이다.
[math(\displaystyle a + x = c + y = b + d = 1)].
이제 다음을 보자.
[math(\displaystyle ac + (bx + ay + dx) = a(c + y) + (b + d)x = a + x = 1)].
여기서 [math(ac \in I_1 \cap I_2)], [math(bx + ay + dx \in J)]임을 보자. 따라서 위 원소는 [math((I_1 \cap I_2) + J)]에 포함된다. 결국 [math(I_1 \cap I_2)]와 [math(J)] 역시 comaximal함을 보였다.
사실 다음을 곧바로 알 수 있다.
굳이 더 덧붙이자면, 수학적 귀납법으로 쉽게 증명할 수 있다.(보조정리 1-2) Comaximal한 two-sided 아이디얼들 [math(I_1)], [math(I_2)], [math(\cdots)], [math(I_n)], [math(J)]에 대하여 [math(\bigcap_i I_i)]와 [math(J)] 역시 comaximal하다. 즉, [math(\left( \bigcap_i I_i \right) + J = R)]이다.
물론 이건 지금 보이려고 하는 것의 [math(n = 2)]인 경우이다. 한편 만약 [math(b + I = 0 + I)], [math(b + J = 1 + J)]인 [math(b \in R)]을 찾았다면, [math(a = x + b(y - x))]로 두는 것으로 증명을 완료할 수 있다. 그런데 [math(b + I = 0 + I)]인 것은 [math(b \in I)]임과 동치이므로 이는 곧 [math(b - 1 \in J)]이도록 하는 [math(b \in I)]를 찾으라는 이야기이다. 그리고 이건 [math(I + J = R)]이라는 사실로부터 금방 해결할 수 있다. 저 가정으로부터 어떤 [math(b \in I)], [math(c \in J)]에 대하여 [math(b + c = 1)]임을 알 수 있다. 그리고 [math(b - 1 = -c \in J)]이므로 이 [math(b)]가 바로 원하는 그 [math(b)]임을 알 수 있다.(보조정리 2) 두 comaximal한 two-sided 아이디얼들 [math(I)], [math(J)], 그리고 임의의 [math(x, y \in R)]에 대하여 [math(a + I = x + I)], [math(a + J = y + J)]인 [math(a \in R)]이 존재한다.
이제 원래 문제로 돌아가자. 언급했듯이 [math(n = 2)]인 경우는 증명이 완료되어 수학적 귀납법의 첫번째 스텝을 잘 밟았음을 안다. 이제 어떤 [math(n)]에 대하여 [math(\phi)]가 항상 전사임이 밝혀졌다고 가정한 다음, comaximal한 two-sided 아이디얼들 [math(I_1)], [math(I_2)], [math(\cdots)], [math(I_{n + 1})]에 대하여 정의된 [math(\phi)] 역시 전사인가를 살펴보도록 하자.
먼저 임의의 [math(a_1, a_2, \cdots, a_{n + 1} \in R)]을 생각해 보자. 그러면 가정에 의하여 모든 [math(i = 1, 2, \cdots, n)]에 대해 [math(a_0 + I_i = a_i + I_i)]인 [math(a_0 \in R)]이 존재한다는 것을 알 수 있다. 이제 보조정리 1-2에 의하여 [math(I_0 = \bigcap_{i = 1}^n I_i)]와 [math(I_{n + 1})]이 comaximal하다는 것을 보자. 그러면 보조정리 2에 의하여 [math(a + I_0 = a_0 + I_0)], [math(a + I_{n + 1} = a_{n + 1} + I_{n + 1})]을 만족하는 [math(a \in R)]을 찾을 수 있다. 그런데 [math(a - a_0 \in I_0 = \bigcap_{i = 1}^n I_i)]이므로 모든 [math(i = 1, 2, \cdots, n)]에 대하여 [math(a + I_i = a_0 + I_i = a_i = I_i)]임을 알 수 있다. 결국 모든 [math(i = 1, 2, \cdots, n + 1)]에 대해 [math(a + I_i = a_i + I_i)]인 [math(a \in R)]을 찾았다. 따라서 이 경우에도 [math(\phi)]는 전사이다.
마지막으로, 수학적 귀납법에 의하여 모든 [math(n)]에 대해 [math(\phi)]가 전사임을 주장할 수 있다.