| 정수론 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] 하권(下卷)에 나오는 문제 중 26번 문제로, 내용은 다음과 같다.今有物，不知其數。三、三數之，賸二；五、五數之，賸三；七、七數之，賸二。問物幾何？
答曰：二十三。
術曰：「三、三數之，賸二」，置一百四十；「五、五數之，賸三」，置六十三；「七、七數之，賸二」，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數之，賸一，則置七十；五，五數之，賸一，則置二十一；七、七數之，賸一，則置十五。一百六以上，以一百五減之，即得。
여기 물건이 있는데 그 개수는 모른다. 셋씩 세면 둘이 남고, 다섯씩 세면 셋이 남고, 일곱씩 세면 둘이 남는다. 이 물건은 몇 개인가?
답: 23.[4]
풀이: '셋씩 세면 둘이 남는다'는 140으로 놓고, '다섯씩 세면 셋이 남는다'는 63으로 놓고, '일곱씩 세면 셋이 남는다'는 30으로 놓는다. 이를 모두 합하여 233을 얻는다. 여기에서 210을 빼면 답을 얻는다.[5] 무릇, 셋씩 세어 하나가 남으면 70으로 놓고, 다섯씩 세어 하나가 남으면 21로 놓고, 일곱씩 세어 하나가 남으면 15로 놓는다. (합이) 106 이상이면 105를 빼서 답을 얻는다.
뭔가 초등학교 문제집에나 나올 법한 느낌이지만[6] 연립 합동식 문제로, KMO 같은 경시대회나 대학교 수학과 2학년 과정인 정수론과 관련된 내용이다. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다. 이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.答曰：二十三。
術曰：「三、三數之，賸二」，置一百四十；「五、五數之，賸三」，置六十三；「七、七數之，賸二」，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數之，賸一，則置七十；五，五數之，賸一，則置二十一；七、七數之，賸一，則置十五。一百六以上，以一百五減之，即得。
여기 물건이 있는데 그 개수는 모른다. 셋씩 세면 둘이 남고, 다섯씩 세면 셋이 남고, 일곱씩 세면 둘이 남는다. 이 물건은 몇 개인가?
답: 23.[4]
풀이: '셋씩 세면 둘이 남는다'는 140으로 놓고, '다섯씩 세면 셋이 남는다'는 63으로 놓고, '일곱씩 세면 셋이 남는다'는 30으로 놓는다. 이를 모두 합하여 233을 얻는다. 여기에서 210을 빼면 답을 얻는다.[5] 무릇, 셋씩 세어 하나가 남으면 70으로 놓고, 다섯씩 세어 하나가 남으면 21로 놓고, 일곱씩 세어 하나가 남으면 15로 놓는다. (합이) 106 이상이면 105를 빼서 답을 얻는다.
아래 정리를 읽기 전에, 이해를 쉽게 하기 위해선 반드시 합동식 문서를 읽고 오자. [math(\bmod)]에 대해 간단히 설명하자면, [math(a\equiv b\pmod c)]는 [math(a)]를 [math(c)]로 나눈 나머지가 [math(b)]라는 뜻으로, 일반적인 방정식 표기로 나타내면 [math(a=ck+b ~ (0\le b<c,\,k\in\Z))]로 나타내고, 증명에 이용할때는 [math(c\mid(a-b))]로 나타낸다.
자세한 정리는 다음과 같다.
[math(m_1,\,m_2,\,\cdots,\,m_n)]이 쌍마다 서로소[7]이면, 다음 연립 합동식
[math(x\equiv\begin{cases} a_1& \pmod{m_1} \\ a_2& \pmod{m_2} \\ a_3& \pmod{m_3} \\ &\vdots \\ a_n& \pmod{m_n} \end{cases})]
은 법 [math(\displaystyle\prod_{i=1}^nm_i = m_1m_2\cdots m_n)]에 대하여 유일한 해를 갖는다.
단순히 연립합동식을 푸는 것보다는 해가 유일하게 '존재'한다는 엄청난 성질을 갖고 있기에 정말 강력한 도구이다.[8][math(x\equiv\begin{cases} a_1& \pmod{m_1} \\ a_2& \pmod{m_2} \\ a_3& \pmod{m_3} \\ &\vdots \\ a_n& \pmod{m_n} \end{cases})]
은 법 [math(\displaystyle\prod_{i=1}^nm_i = m_1m_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(\displaystyle\prod_{i=1}^na_i)]는 서로소이다.
- 증명
- 서로소가 아니라고 가정하자. 그럼 [math(m)]과 [math(\displaystyle\prod_{i=1}^na_i)]의 공약수인 소수 [math(p)]가 존재한다. [math(\displaystyle p\Biggm|\prod_{i=1}^na_i)]이므로 [math(p\mid a_i)]인 [math(a_i)]가 존재한다. 그러면 [math(a_i)]와 [math(m)]은 모두 [math(p)]로 나누어 떨어지고, 이는 서로소가 아니라는 가정에 모순이므로 가정이 틀렸다.
2. 양의 정수 [math(m)]과 [math(a_1,\,a_2,\,\cdots,\,a_n)]에 대하여 [math(m)]이 [math(a_1,\,a_2,\,\cdots,\,a_n)]의 각각의 배수이면 [math(m)]은 [math(\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n))]의 배수이다.
- 증명
- 나눗셈 정리에 의하여
을 만족하는 정수 [math(q)], [math(r)]이 유일하게 존재한다. 그런데 [math(m)]과 [math(\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n))]이 모두 [math(a_i)]로 나누어 떨어지므로, [math(r)]도 [math(a_i)]로 나누어 떨어져야 한다. 이것은 모든 [math(i)]에 대해 참이므로 [math(r)]은 [math(\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n))]보다 작은 [math(a_i)]들의 공배수이다. 이걸 만족하는 값은 [math(r=0)]밖에 없으며, 이는 곧 [math(m)]이 [math(\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n))]의 배수임을 의미한다.[math(m = q{\cdot}\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n)+r)]
(단, [math(0\le r<\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n))])
3. 양의 정수 [math(a_1,\,a_2,\,\cdots,\,a_n)]에 대하여 [math(\gcd(a_i,\,a_j) = 1 ~ (i\ne j))][9]이면, [math(\displaystyle\operatorname{lcm}(a_1,\,a_2,\,\cdots,\,a_n) = \prod_{i=1}^na_i)]이다.
- 증명
- 이에 대한 증명은 최소공배수 참조. 사실 증명이라 할 것도 없다.
2.2. 존재성
| [math(\begin{aligned} m &= \prod_{i=1}^nm_i \\ &= m_1m_2\cdots m_n\end{aligned})] |
도움정리의 1로부터 [math(\gcd(n_k,\,m_k) = 1)]이다. 그럼 베주 항등식에 의해,
| [math(s_kn_k + t_km_k =1)] |
| [math(s_kn_k \equiv 1 \pmod{m_k})] |
| [math(\begin{aligned} x &= \sum_{i=1}^na_in_is_i \\ &= a_1n_1s_1 + a_2n_2s_2 + \cdots + a_nn_ns_n\end{aligned})] |
| [math(\begin{aligned} x&\equiv a_kn_ks_k \\ &\equiv a_k{\cdot}1 = a_k\pmod{m_k}\end{aligned})] (단, [math(k\in\N,\,1\leq k\leq n)]) |
즉, [math(x)]는 주어진 연립 합동식의 한 해이다.
2.3. 유일성
[math(x)], [math(y)]가 주어진 연립 합동식의 해라고 하자.[12] 그러면,| [math(\begin{aligned} x&\equiv a_1\pmod{m_1} &&& y &\equiv a_1\pmod{m_1} \\ x&\equiv a_2\pmod{m_2} &&& y&\equiv a_2\pmod{m_2} \\ && \vdots \\ x&\equiv a_n\pmod{m_n} &&& y&\equiv a_n\pmod{m_n}\end{aligned})] |
| [math(\operatorname{lcm}(m_1,\,m_2,\,\cdots,\,m_n)\mid(x-y))] |
| [math(\displaystyle\prod_{i=1}^nm_i \Biggm|(x-y))] |
| [math(\displaystyle x\equiv y\left(\mathrel{\bmod}{\prod_{i=1}^nm_i}\right))] |
3. 문제를 푸는 방법
위의 손자산경에 나온 문제를 풀어보도록 하자. 먼저 연립 합동식으로 다시 쓰면| [math(x \equiv \begin{cases} 2\pmod3 \\ 3\pmod5 \\ 2\pmod7\end{cases})] |
3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 [math(3\times5\times7=105)]에 대하여 유일한 해를 가진다. [math(m=105)], [math(n_1=35)], [math(n_2=21)], [math(n_3=15)]라 하자.
| [math(\begin{aligned} n_1s_1 &\equiv 35s_1 \equiv 2s_1 \equiv 1\pmod3 \\ n_2s_2 &\equiv 21s_2 \equiv s_2 \equiv 1\pmod5 \\ n_3s_3 &\equiv 15s_3 \equiv s_3 \equiv 1\pmod7 \end{aligned})] |
| [math(\begin{aligned} x &\equiv a_1n_1s_1 + a_2n_2s_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 \pmod{105} \end{aligned})] |
따라서 [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 sided ideal) [math(I_1,\,\cdots,\,I_n)]을 생각하자. [math(\{I_i\colon i=1,\,\cdots,\,n\})]이 공동극대(comaximal)[15]라고 하자. 그러면, [math(\displaystyle R/{\left(\bigcap_iI_i\right)} \cong \prod_i(R/I_i))]이다. (여기서 [math(\displaystyle \prod_i(R/I_i))]에 성분별로(componentwise) 연산하는 환 구조[16] 주었다.)
특히, 임의의 [math(a \in R)]에 대해 [math(\displaystyle a + \bigcap_iI_i \in R/{\left(\bigcap_iI_i\right)})]을 [math(\displaystyle (a + I_1,\,a + I_2,\,\cdots,\,a + I_n) \in \prod_i(R/I_i))]로 보내는 사상은 잘 정의된 환 동형사상(ring isomorphism)이다.
특히, 임의의 [math(a \in R)]에 대해 [math(\displaystyle a + \bigcap_iI_i \in R/{\left(\bigcap_iI_i\right)})]을 [math(\displaystyle (a + I_1,\,a + I_2,\,\cdots,\,a + I_n) \in \prod_i(R/I_i))]로 보내는 사상은 잘 정의된 환 동형사상(ring isomorphism)이다.
중국인의 나머지 정리와 전혀 안 똑같아 보이지만, 단계적으로 접근하여 이 모티브를 확인할 수 있다. 이를 위해 [math(R)]이 주 아이디얼 정역(principal ideal domain)인 경우에 집중해 보자. 이 경우 각 [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 \pmod{p_i} \iff a + (p_i) = b + (p_i))].
이제 어떤 원소들 [math(a_i)]들에 대하여 다음과 같이 쓸 수 있다.모든 [math(i)]에 대하여 [math(a \equiv a_i \pmod{p_i} \iff)] 모든 [math(i)]에 대하여 [math(a + I_i = a_i + I_i)].
한편 임의의 [math(a_i \in R)]들에 대하여 [math((\displaystyle a_1 + I_1,\,a_2 + I_2,\,\cdots,\,a_n + I_n) \in \prod_i(R/I_i))]가 항상 존재하며, 반대로 당연하지만 [math(\displaystyle\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(p_i)]들과 임의의 [math(a_i \in R)]이 주어져 있을 때 모든 [math(i)]에 대하여 [math(a \equiv a_i \pmod{p_i})]인 [math(a \in R)]이 존재하는가? 존재한다면 유일한가?
[math(R = \Z)]일 때 이 질문에 대한 답이 중국인의 나머지 정리에 의해 주어진다는 것을 알 수 있다. [math(a)]가 유일하지는 않지만 대신에 법 [math(\displaystyle\prod_{i=1}^np_i)]에 대해 유일하다는 것은 안다. 그런데 사실 [math(R)]이 주 아이디얼 정역인 상황에서 두 [math(a,\,b \in R)]에 대하여 [math(\displaystyle a \equiv b \left(\bmod\prod_{i=1}^np_i\right))]인 필요충분조건은 [math(\displaystyle a + \bigcap_i I_i = b + \bigcap_i I_i)]인 것이다.이제 위 질문을 다음과 같이 환의 언어로 번역할 수 있음을 보자.
아이디얼 [math(I_i)]들과 임의의 [math((\displaystyle 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)], [math(b)]를 찾았다면 [math(\displaystyle a + \bigcap_i I_i = b + \bigcap_i I_i)]임을 알 수 있다.여기서 더 나아가 보자. 다음과 같은 사상을 정의할 수 있다.
| [math(\displaystyle \phi\colon R \to \prod_i (R/I_i) \\ \phi(a) = (a + I_1,\,a + I_2,\,\cdots,\,a + I_n))] |
서로소인 아이디얼 [math(I_i)]들이 주어져 있고 위와 같이 환 준동형사상 [math(\phi)]가 정의되어 있을 때, [math(\phi)]는 전사(surjective)인가? 그리고 [math(\ker\phi)]는 무엇인가?[17]
그리고 중국인의 나머지 정리에 따라 일단 [math(R = \Z)]인 경우에 한하여 답이 다음과 같음을, 즉 중국인의 나머지 정리를 환과 사상의 언어로 번역한 결과물이 다음과 같음을 알 수 있다.[math(\phi)]는 전사이며 [math(\displaystyle\ker\phi = \bigcap_i I_i)]이다.
여기에 제1 동형 정리까지 끼얹으면 결국 중국인의 나머지 정리를 최종적으로 다음과 같이 번역할 수 있다.서로서인 아이디얼들 [math(I_i ~ (i = 1,\,2,\,\cdots,\,n))]이 주어져 있고 사상 [math(\displaystyle\tilde\phi\colon R/{\left( \bigcap_i I_i \right)} \to \prod_i(R/I_i))]가 [math(\displaystyle\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)]은 주 아이디얼 정역이라는 가정이 아무래도 상관 없어졌음을 알 수 있다. 여기서 이 가정까지 지우는 것으로 중국인의 나머지 정리 최종 일반화를 얻을 수 있다.다만 이건 그냥 중국인 나머지 정리에 해당하는 명제를 환과 사상의 언어로 번역하고 일반화한 것에 불과하다. 그리고 그 과정 중에서 사용된 일반화들에 대한 정당화, 그러니까 증명 같은 게 일절 없었음을 보자. 무슨 소리냐면 이걸 증명하는 건 또다른 문제라는 것이다. 다행히 증명은 그리 어렵지 않다. 그리고 다소 복잡해 보이는 최종 버전 말고 그 바로 전 버전, 즉 [math(\bm\phi)]는 전사이며 [math(\displaystyle\bm{\ker\phi = \bigcap_i I_i})]임만 보이면 된다. 다시, 제1 동형 정리에 의하여 이걸 보이면 최종 버전이 바로 성립하기 때문이다. 이는 아래 단락에서 설명하도록 하겠다.
이게 무슨 지적유희냐고 할 수 있겠지만, 이러한 일반화를 통해 정수론이 아닌 다른 영역에서도 중국인의 나머지 정리와 비슷한 결과를 얻을 수 있다는 점이 중요하다. 물론 환과 사상의 언어로 번역을 한다는 게 결국 그런 의미이긴 하다. 예를 들어 다음을 얻을 수 있다.[18]
서로소인 다항식들 [math(p_i(t))]와 임의의 다항식들 [math(g_i(t))]에 대하여 [math(f(t) \equiv g_i(t) \pmod{p_i(t)})]인 다항식 [math(f(t))]가 존재하며, 유일[math(\Biggl()]up to modulo [math(\displaystyle\prod_i p_i(t)\Biggr))]하다.
마지막으로 하나 더, 아마 몇몇 사람들은 저 정리에서 가환환이라는 조건이 없다는 것을 눈치챘을 것이다.[19] 실제로 그 조건마저 없애는 (대신에 물론 양쪽 아이디얼들만 생각하는) 일반화까지 가능하다는 것을 아래 증명으로부터 볼 수 있다.5.1. 증명
그 중에서도 쉬운 쪽인 [math(\displaystyle\ker\phi = \bigcap_i I_i)]를 먼저 확인해 보자. 다음 몇 줄로 간단하게 증명된다.| [math(a \in \ker\phi \\ \iff \phi(a) = (a + I_1,\,a + I_2,\,\cdots,\,a + I_n) = 0)] [math(\iff)] 모든 [math(i)]에 대해 [math(a \in I_i)] [math(\iff)] [math(\displaystyle a \in \bigcap_i I_i)] |
(보조정리 1-1) 공동극대인 세 양쪽아이디얼들 [math(I_1)], [math(I_2)], [math(J)]에 대하여 [math(I_1 \cap I_2)]와 [math(J)] 역시 공동극대이다. 즉, [math((I_1 \cap I_2) + J = R)]이다.
[math((I_1 \cap I_2) + J)]이 단위원 1을 가진다는 것을 보이는 것으로 증명을 해 보이도록 하겠다.[20] 공동극대라는 가정으로부터 다음을 만족하는 [math(a,\,b \in I_1)], [math(c,\,d \in I_2)], [math(x,\,y \in J)]를 찾을 수 있다.| [math(a + x = c + y = b + d = 1)] |
| [math(ac + (bx + ay + dx) = a(c + y) + (b + d)x = a + x = 1)] |
사실 다음을 곧바로 알 수 있다.
(보조정리 1-2) 공동극대인 양쪽아이디얼들 [math(I_1,\,I_2,\,\cdots,\,I_n)], [math(J)]에 대하여 [math(\displaystyle\bigcap_i I_i)]와 [math(J)] 역시 공동극대이다. 즉, [math(\displaystyle\left( \bigcap_i I_i \right) + J = R)]이다.
굳이 더 덧붙이자면, 수학적 귀납법으로 쉽게 증명할 수 있다.(보조정리 2) 두 공동극대인 양쪽아이디얼들 [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)]가 항상 전사임이 밝혀졌다고 가정한 다음, 공동극대인 양쪽아이디얼들 [math(I_1,\,I_2,\,\cdots,\,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(\displaystyle I_0 = \bigcap_{i=1}^n I_i)]와 [math(I_{n + 1})]이 공동극대라는 것을 보자. 그러면 보조정리 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(\displaystyle 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] 중국의 옛 수학서에는 이 『손자산경(孫子算經)』 외에도 『주비산경(周髀算經)』, 『구장산술(九章算術)』, 『해도산경(海島算經)』, 『오조산경(五曹算經)』, 『하후양산경(夏侯陽算經)』, 『장구건산경(張邱建算經)』, 『오경산술(五經算術)』, 『집고산경(緝古算經)』, 『철술(綴術)』 등이 있다. 이들을 통틀어 '산경십서(算經十書)'로 칭한다.[4] 현대수학 관점에서 답을 엄밀하게 적으면 [math(105k+23~(k\ge0))]이다.[5] 참고로 어떤 원리에 따라 140, 63, 30이라는 숫자가 나왔는지 구체적인 설명이 없으나, 후술할 연립 합동식의 풀이에서 얻어지는 값이기는 하다. 즉, '풀이'라고는 되어있으나 엄밀하게 따지면 풀이과정이 생략되어있는 상황에 가깝다.[6] 그런데 그것이 실제로 일어난다. 초등학교 문제집에 이런 문제들이 나오고, 심지어 중학교 방정식 단원에 나오는 경우도 있다. 보통 이런 문제가 저학년 수준에서 나오면 나머지가 일정하거나 해서 그나마 쉽게 풀리도록 난이도를 조절해 놓는 경우가 많다.[7] 즉, [math(i\ne j)]일 때, [math(\gcd(m_i,\,m_j)=1)][8] 덕에 중등 KMO 2차에서 자주 쓰인다. 단순히 해가 존재한다는 것을 보이려고. 예를 들면 "연속된 100개의 수가 1000개의 약수를 가질 수 있는가?" 등이 있다.[9] 즉, 쌍마다 서로 소(pairwise relatively prime)[10] 나머지 [math(a_jn_js_j)]는 [math(m_k)]로 나누면 나머지가 0 이므로 [math(j=k)]인 경우만 생각해 주면 된다.[11] 또한 [math(n_ks_k)]는 위 [math(s_kn_k\equiv 1\pmod{m_k})]와 합동식의 성질 때문에 1로 바뀐다.[12] 임의의 두 답이 같음을 보이는 방법은 유일성을 증명하는 데 자주 쓰이는 테크닉이다.[13] 추이율. 합동식의 성질 참조[14] 여러 값 중 아무거나 고르면 되는데, 첫 번째 합동식은 [math(35s_1 \equiv -s_1 \equiv 1\pmod3)]으로도 나타낼 수도 있어 [math(s_1 = -1)]도 가능하며, 아래 계산식에서 [math(s_1 = -1)]을 대입하면 [math(x \equiv 23\pmod{105})]를 바로 얻어낼 수 있다.[15] '서로소(coprime)인 아이디얼'이라고도 하며, 임의의 [math(i\ne j)]에 대해 [math(I_i+I_j=R)]인 것을 의미한다.[16] 예를 들어 두 환 [math(R_1)], [math(R_2)]에 대하여 [math(R_1 \times R_2)]에다 다음과 같은 합과 곱을 주었다는 뜻이다.
[math(\begin{aligned} (a,\,b) + (c,\,d) &\equiv (a+c,\,b+d) \\ (a,\,b) \cdot (c,\,d) &\equiv (ac,\,bd) \end{aligned})].[17] 많은 경우 주어진 사상(map)이 전사인가 하는 질문은 존재성과 연결되며, 단사(injection)인가 혹은 그 핵(kernel)이 무엇인가 하는 질문은 유일성과 연결된다.[18] 일변수 다항식들의 환(polynomial ring) 또한 주 아이디얼 정역임을 기억하자.[19] 양쪽아이디얼이라고 굳이 쓴 것이 힌트이다. 가환환에서는 좌 아이디얼(left-sided), 우 아이디얼(right-sided), 양쪽 아이디얼(two-sided) 모두가 동치이고, 따라서 굳이 안 써준다.[20] 단위원을 가진 아이디얼은 전체 환 하나 뿐이다.
[math(\begin{aligned} (a,\,b) + (c,\,d) &\equiv (a+c,\,b+d) \\ (a,\,b) \cdot (c,\,d) &\equiv (ac,\,bd) \end{aligned})].[17] 많은 경우 주어진 사상(map)이 전사인가 하는 질문은 존재성과 연결되며, 단사(injection)인가 혹은 그 핵(kernel)이 무엇인가 하는 질문은 유일성과 연결된다.[18] 일변수 다항식들의 환(polynomial ring) 또한 주 아이디얼 정역임을 기억하자.[19] 양쪽아이디얼이라고 굳이 쓴 것이 힌트이다. 가환환에서는 좌 아이디얼(left-sided), 우 아이디얼(right-sided), 양쪽 아이디얼(two-sided) 모두가 동치이고, 따라서 굳이 안 써준다.[20] 단위원을 가진 아이디얼은 전체 환 하나 뿐이다.