중국인의 나머지 정리

今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問物幾何？
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 (정)수는 무엇인가?[4]

[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)]에 대하여 유일한 해를 갖는다.

양의 정수 [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)]을 모두 나누고, 이는 가정에 모순이다.

양의 정수 [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))]의 배수임을 보인다.

양의 정수 [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(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 \equiv b \;\; (\textrm{mod }p_i) \;\;\; \leftrightarrow \;\;\; a + (p_i) = b + (p_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(p_i)]들과 임의의 [math(a_i \in R)]이 주어져 있을 때 모든 [math(i)]에 대하여 [math(a \equiv a_i \;\; (\textrm{mod }p_i))]인 [math(a \in R)]이 존재하는가? 존재한다면 유일한가?

아이디얼 [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)]이 존재하는가? 존재한다면 유일한가?

Comaximal한 아이디얼 [math(I_i)]들이 주어져 있고 위와 같이 환 준동형사상 [math(\phi)]가 정의되어 있을 때, [math(\phi)]는 전사(surjective)인가? 그리고 [math(\ker \phi)]는 무엇인가?[15]

[math(\phi)]는 전사이며 [math(\ker \phi = \bigcap_i I_i)]이다.

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(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))])하다.

(보조정리 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)]이다.

(보조정리 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)]이 존재한다.