| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
중국인의 나머지 정리(Chinese remainder theorem; CRT)[1]는 남북조시대 중국의 5세기 문헌인 『손자산경(孫子算經)』[2][3]에는 나오는 문제로, 내용은 다음과 같다.今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問物幾何？
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 (정)수는 무엇인가?[4]
뭔가 초등학교 문제집에나 나올 법한 느낌이지만[5] 연립 합동식 문제로, KMO 같은 경시대회나 대학교 수학과 2학년 과정인 정수론과 관련된 내용이다. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다. 이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 (정)수는 무엇인가?[4]
아래 정리를 읽기 전에, 이해를 쉽게 하기 위해선 반드시 합동식 문서를 읽고 오자. mod에 대해 간단히 설명하자면, [math(A\,(\operatorname{mod}B))]이면 [math(B)]로 나누어 [math(A)]의 나머지를 생기게 하는 수라는 뜻이다. [math(C\equiv A\,(\operatorname{mod}B))]라면, 일반적인 방정식으로는 [math(C=Bk+A)], [math(0\le A<B)], [math(k\in\Z)]로 나타내고, 증명에 이용할때는 [math(B\mid(C-A))]로 나타낸다.
자세한 정리는 다음과 같다.
[math(m_1)], [math(m_2)], [math(\cdots)], [math(m_n)]이 쌍마다 서로소(즉, [math(\gcd(m_i,m_j)=1)], [math(i\ne j)])이면, 다음 연립 합동식
[math(x\equiv a_1\,(\operatorname{mod}m_1))]
[math(x\equiv a_2\,(\operatorname{mod}m_2))]
[math(x\equiv a_3\,(\operatorname{mod}m_3))]
[math(\vdots)]
[math(x\equiv a_n\,(\operatorname{mod}m_n))]
은 법 [math(m_1 m_2\cdots m_n)]에 대하여 유일한 해를 갖는다.
단순히 연립합동식을 푸는 것보다는 해가 유일하게 '존재'한다는 엄청난 성질을 갖고 있기에 정말 강력한 도구이다.[6][math(x\equiv a_1\,(\operatorname{mod}m_1))]
[math(x\equiv a_2\,(\operatorname{mod}m_2))]
[math(x\equiv a_3\,(\operatorname{mod}m_3))]
[math(\vdots)]
[math(x\equiv a_n\,(\operatorname{mod}m_n))]
은 법 [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)]이 성립한다.
이에 대한 증명은 최소공배수 참조. 사실 증명이라 할 것도 없다.[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(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 \equiv b \;\; (\textrm{mod }p_i) \;\;\; \leftrightarrow \;\;\; a + (p_i) = b + (p_i))].
이제 어떤 원소들 [math(a_i)]들에 대하여 다음과 같이 쓸 수 있다.모든 [math(i)]에 대하여 [math(a \equiv a_i \;\; (\textrm{mod }p_i))]
[math(\leftrightarrow)] 모든 [math(i)]에 대하여 [math(a + I_i = a_i + I_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(\leftrightarrow)] 모든 [math(i)]에 대하여 [math(a + I_i = a_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(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(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(R = \Z)]인 경우에 한하여 해당 [math(a)]가 존재하며, 만약 어떤 두 답 [math(a, b)]를 찾았다면 [math(a + \bigcap_i I_i = b + \bigcap_i I_i)]임을 알 수 있다.여기서 더 나아가 보자. 다음과 같은 사상을 정의할 수 있다.
[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)의 언어까지 추가하여 위 문제를 다음과 같이 번역할 수 있음을 보자.
Comaximal한 아이디얼 [math(I_i)]들이 주어져 있고 위와 같이 환 준동형사상 [math(\phi)]가 정의되어 있을 때, [math(\phi)]는 전사(surjective)인가? 그리고 [math(\ker \phi)]는 무엇인가?[15]
그리고 중국인의 나머지 정리에 따라 일단 [math(R = \Z)]인 경우에 한하여 답이 다음과 같음을, 즉 중국인의 나머지 정리를 환과 사상의 언어로 번역한 결과물이 다음과 같음을 알 수 있다.[math(\phi)]는 전사이며 [math(\ker \phi = \bigcap_i I_i)]이다.
여기에 제1 동형 정리까지 끼얹으면 결국 중국인의 나머지 정리를 최종적으로 다음과 같이 번역할 수 있다.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(R)]은 PID라는 가정이 아무래도 상관 없어졌음을 알 수 있다. 여기서 이 가정까지 지우는 것으로 중국인의 나머지 정리 최종 일반화를 얻을 수 있다.다만 이건 그냥 중국인 나머지 정리에 해당하는 명제를 환과 사상의 언어로 번역하고 일반화한 것에 불과하다. 그리고 그 과정 중에서 사용된 일반화들에 대한 정당화, 그러니까 증명 같은 게 일절 없었음을 보자. 무슨 소리냐면 이걸 증명하는 건 또다른 문제라는 것이다. 다행히 증명은 그리 어렵지 않다. 그리고 다소 복잡해 보이는 최종 버전 말고 그 바로 전 버전, 즉 [math(\phi)]는 전사이며 [math(\ker \phi = \bigcap_i I_i)]임만 보이면 된다. 다시, 제1 동형 정리에 의하여 이걸 보이면 최종 버전이 바로 성립하기 때문이다. 이는 아래 단락에서 설명하도록 하겠다.
이게 무슨 지적유희냐고 할 수 있겠지만, 이러한 일반화를 통해 정수론이 아닌 다른 영역에서도 중국인의 나머지 정리와 비슷한 결과를 얻을 수 있다는 점이 중요하다. 물론 환과 사상의 언어로 번역을 한다는 게 결국 그런 의미이긴 하다. 예를 들어 다음을 얻을 수 있다.[16]
서로소인 다항식들 [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))])하다.
마지막으로 하나 더, 아마 몇몇 사람들은 저 정리에서 가환환이라는 조건이 없다는 것을 눈치챘을 것이다.[17] 실제로 그 조건마저 없애는 (대신에 물론 two-sided ideal들만 생각하는) 일반화까지 가능하다는 것을 아래 증명으로부터 볼 수 있다.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)]에 대한 수학적 귀납법으로 전사임을 보이는 쓰는 방식을 쓸 것이다.
(보조정리 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((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)]를 찾을 수 있다.[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)]이다.
굳이 더 덧붙이자면, 수학적 귀납법으로 쉽게 증명할 수 있다.(보조정리 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(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)]임을 알 수 있다.이제 원래 문제로 돌아가자. 언급했듯이 [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)]가 전사임을 주장할 수 있다.
6. 관련 링크
##
7. 관련 문서
[1] Chinese는 꼭 중국'인'만이 아니라 중국과 관련한 것 일체를 나타내는 말이므로 썩 좋은 번역은 아니다. '중국식 나머지 정리'라고 했으면 적절했을 것이다. 아니면 직설적으로 손자산경 나머지 정리라고 하든지.[2] 손자병법을 쓴 그 손자와 같은 손씨이다. 단, 손자산경을 쓴 사람은 한참 후대의 인물.[3] 중국의 옛 수학서에는 이 『손자산경(孫子算經)』 외에도 『주비산경(周髀算經)』, 『9장산술(九章算術)』, 『해도산경(海島算經)』, 『5조산경(五曹算經)』, 『하후양산경(夏侯陽算經)』, 『장구건산경(張邱建算經)』, 『5경산술(五經算術)』, 『집고산경(緝古算經)』, 『철술(綴術)』 등이 있다. 이들을 통틀어 '산경10서(算經十書)'로 칭한다.[4] 참고로 답은 [math(105k+23)], [math(k\ge0)]이다.[5] 그런데 그것이 실제로 일어난다. 초등학교 문제집에 이런 문제들이 나오고, 심지어 중학교 방정식 단원에 나오는 경우도 있다. 보통 이런 문제가 저학년 수준에서 나오면 나머지가 일정하거나 해서 그나마 쉽게 풀리도록 난이도를 조절해 놓는 경우가 많다.[6] 덕에 중등 KMO 2차에서 자주 쓰인다. 단순히 해가 존재한다는 것을 보이려고. 예를 들면 "연속된 100개의 수가 1000개의 약수를 가질 수 있는가?" 등이 있다.[7] [math(n_k)]의 정의 때문에 성립[8] 나머지 [math(a_j n_j s_j)]는 [math(m_k)]로 나누면 나머지가 0 이므로 [math(j=k)]인 경우만 생각해 주면 된다.[9] 또한 [math(n_k s_k)]는 위 [math(s_k n_k\equiv 1\left(\text{mod}\,m_k\right))]와 합동식의 성질 때문에 1로 바뀐다.[10] 임의의 두 답이 같음을 보이는 방법은 유일성을 증명하는 데 자주 쓰이는 테크닉이다.[11] 추이율. 합동식의 성질 참조[12] 여러 값 중 아무거나 고르면 된다.[13] 임의의 [math(i\ne j)]에 대해, [math(I_{i}+I_{j}=R)][14] 예를 들어 두 환 [math(R_1)], [math(R_2)]에 대하여 [math(R_1 \times R_2)]에다 다음과 같은 합과 곱을 주었다는 뜻이다. [math((a, b) + (c, d) \equiv (a+c, b+d))], [math((a, b) \cdot (c, d) \equiv (ac, bd))].[15] 많은 경우 주어진 사상(map)이 전사인가 하는 질문은 존재성과 연결되며, 단사(injection)인가 혹은 그 kernel이 무엇인가 하는 질문은 유일성과 연결된다.[16] 일변수 다항식들의 환(polynomial ring) 또한 PID임을 기억하자.[17] Two-sided 아이디얼이라고 굳이 쓴 것이 힌트이다. 가환환에서는 left-sided, right-sided, two-sided 모두가 동치이고, 따라서 굳이 안 써준다.[18] 단위원을 가진 아이디얼은 전체 환 하나 뿐이다.