중국인의 나머지 정리

수론과 환론에서 중국인의 나머지 정리(中國人-定理, 틀:Llang)는 서로소 아이디얼들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 서로소 자연수들에 대한 연립 합동식의 해의 유일한 존재에 대한 정리이다.

정의

일반적 가환환에 대한 경우

어떤 환 $R$ 속의 두 아이디얼 $𝔞, 𝔟 \subset R$ 가 $𝔞 + 𝔟 = R$ 를 만족시키면, 이 두 아이디얼을 서로소(틀:Llang)라고 한다.

$R$ 가 (곱셈 단위원을 갖는) 가환환이라고 하고, $𝔫_{1}, \dots, 𝔫_{k} \subset R$ 가 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을

𝔫 = \prod_{i = 1}^{k} 𝔫_{i}

라고 놓자. 그렇다면 다음이 성립한다.

𝔫 = ⋂_{i = 1}^{k} 𝔫_{i}

R / 𝔫 ≅ \prod_{i = 1}^{k} R / 𝔫_{i}

여기서, 환 동형사상은 구체적으로 다음과 같다.

r + 𝔫 \mapsto (r + 𝔫_{1}, \dots, r + 𝔫_{k})

정수환에 대한 경우

일반적 가환환에 대한 중국인의 나머지 정리를 정수의 환 $ℤ$ 에 대하여 적용하여, 정수론적인 용어로 쓰면 다음과 같다. 이 경우, 아이디얼은 자연수(음이 아닌 정수)로, 서로소 아이디얼은 서로소 자연수로 번역할 수 있다.

서로소인 음이 아닌 정수 $n_{1}, n_{2}, \dots, n_{k}$ 가 주어졌다고 하고,

n = \prod_{i = 1}^{k} n_{i}

로 놓자. 그렇다면, 임의의 합동류들의 $k$ -튜플

(a_{1}, a_{2}, \dots, a_{k}) \in \prod_{i = 1}^{k} ℤ / n_{i}

가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해 $a \in ℤ / n$ 이 항상 유일하게 존재한다.

a \equiv a_{i} (\mod n_{i}) \forall i = 1, \dots, k

이에 따라서, 다음과 같은 환 동형사상이 존재한다.

ℤ / n ≅ \prod_{i = 1}^{k} ℤ / n_{i}

증명

여기서는 환이 정수환 $ℤ$ 인 경우만 증명한다. 각 $n_{i}$ 에 대해, $n / n_{i}$ 와 $n_{i}$ 는 서로소이기 때문에, $r_{i} n_{i} + s_{i} (n / n_{i}) = 1$ 인 정수 $r_{i}, s_{i}$ 가 존재한다. 여기에서 $e_{i} = s_{i} (n / n_{i})$ 라고 놓으면,

e_{i} \equiv 1 (\mod n_{i})

e_{i} \equiv 0 (\mod n_{j}) (i \neq j)

가 성립한다.

여기에서 $a = \sum_{i} a_{i} e_{i}$ 로 놓으면, 임의의 $i$ 에 대해 $a \equiv a_{i} (\mod n_{i})$ 가 성립한다. 즉, $a$ 가 바로 구하는 해 중의 하나이다.

이제 $ℤ / n$ 속에서의 유일성을 증명하기 위해, 두 해 $x, y$ 가 존재한다고 가정하자. 그러면 $x \equiv a_{i}, y \equiv a_{i} (\mod n_{i})$ 이므로 $x - y$ 는 모든 $n_{i}$ 의 배수이고, 따라서 $x - y$ 는 $n_{1} n_{2} \dots n_{k} = n$ 의 배수이다. 즉, $x \equiv y (\mod n)$ 이므로, $ℤ / n$ 속에서는 항상 유일한 해가 존재한다.

역사

이 정리는 원래 5세기 남북조 시대의 중국 수학서 《손자산경》(孫子算經)에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같다. 틀:인용문2 즉, 이는 다음과 같은 연립 합동 방정식에 관한 문제이다.

x \equiv 2 (\mod 3) \equiv 3 (\mod 5) \equiv 2 (\mod 7)

이 경우, 풀이에 따라

x \equiv 23 (\mod 3 \cdot 5 \cdot 7 = 105)

이다. 풀이에서 사용된 수는

140 \equiv 2 (\mod 3) \equiv 0 (\mod 5) \equiv 0 (\mod 7)

63 \equiv 0 (\mod 3) \equiv 3 (\mod 5) \equiv 0 (\mod 7)

30 \equiv 0 (\mod 3) \equiv 0 (\mod 5) \equiv 2 (\mod 7)

이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.

이후 이러한 연립 합동 방정식의 문제의 해법은 1247년 남송의 수학자 진구소(秦九韶)가 저술한 《수서구장》(數書九章)에서 더 일반화되었다.

참고 문헌

같이 보기

외부 링크

틀:전거 통제

중국인의 나머지 정리

목차

정의

일반적 가환환에 대한 경우

정수환에 대한 경우

증명

역사

참고 문헌

같이 보기

외부 링크

둘러보기 메뉴

중국인의 나머지 정리

정의

일반적 가환환에 대한 경우

정수환에 대한 경우

증명

역사

참고 문헌

같이 보기

외부 링크

둘러보기 메뉴

검색