청나라 때 출판된 《손자산경 》 사본. 중국인의 나머지 정리는 《손자산경》에서 최초로 언급되었다.수론 과 환론 에서 중국인의 나머지 정리 (中國人-定理, 영어 : Chinese remainder theorem )는 서로소 아이디얼 들에 대한 몫환들의 곱에 대한 정리이다. 즉, 수론적 용어로 쓰면, 어떤 서로소 자연수들에 대한 연립 합동식 의 해의 유일한 존재에 대한 정리이다.
어떤 환
R
{\displaystyle R}
a
,
b
⊂
R
{\displaystyle {\mathfrak {a}},{\mathfrak {b}}\subset R}
a
+
b
=
R
{\displaystyle {\mathfrak {a}}+{\mathfrak {b}}=R}
서로소 (영어 : coprime )라고 한다.
R
{\displaystyle R}
가환환 이라고 하고,
n
1
,
…
,
n
k
⊂
R
{\displaystyle {\mathfrak {n}}_{1},\dots ,{\mathfrak {n}}_{k}\subset R}
아이디얼 들이라고 하자. 또한, 이 아이디얼들의 곱을
n
=
∏
i
=
1
k
n
i
{\displaystyle {\mathfrak {n}}=\prod _{i=1}^{k}{\mathfrak {n}}_{i}}
라고 놓자. 그렇다면 다음이 성립한다.
n
=
⋂
i
=
1
k
n
i
{\displaystyle {\mathfrak {n}}=\bigcap _{i=1}^{k}{\mathfrak {n}}_{i}}
R
/
n
≅
∏
i
=
1
k
R
/
n
i
{\displaystyle R/{\mathfrak {n}}\cong \prod _{i=1}^{k}R/{\mathfrak {n}}_{i}}
여기서, 환 동형사상은 구체적으로 다음과 같다.
r
+
n
↦
(
r
+
n
1
,
…
,
r
+
n
k
)
{\displaystyle r+{\mathfrak {n}}\mapsto (r+{\mathfrak {n}}_{1},\dots ,r+{\mathfrak {n}}_{k})}
일반적 가환환에 대한 중국인의 나머지 정리를 정수의 환
Z
{\displaystyle \mathbb {Z} }
정수론 적인 용어로 쓰면 다음과 같다. 이 경우, 아이디얼 은 자연수(음이 아닌 정수)로, 서로소 아이디얼은 서로소 자연수 로 번역할 수 있다.
서로소인 음이 아닌 정수
n
1
,
n
2
,
⋯
,
n
k
{\displaystyle n_{1},n_{2},\cdots ,n_{k}}
n
=
∏
i
=
1
k
n
i
{\displaystyle n=\prod _{i=1}^{k}n_{i}}
로 놓자. 그렇다면, 임의의 합동류들의
k
{\displaystyle k}
튜플
(
a
1
,
a
2
,
…
,
a
k
)
∈
∏
i
=
1
k
Z
/
n
i
{\displaystyle (a_{1},a_{2},\dots ,a_{k})\in \prod _{i=1}^{k}\mathbb {Z} /n_{i}}
가 주어졌을 때, 다음과 같은 연립 합동 방정식의 해
a
∈
Z
/
n
{\displaystyle a\in \mathbb {Z} /n}
a
≡
a
i
(
mod
n
i
)
∀
i
=
1
,
…
,
k
{\displaystyle a\equiv a_{i}{\pmod {n_{i}}}\quad \forall i=1,\dots ,k}
이에 따라서, 다음과 같은 환 동형사상이 존재한다.
Z
/
n
≅
∏
i
=
1
k
Z
/
n
i
{\displaystyle \mathbb {Z} /n\cong \prod _{i=1}^{k}\mathbb {Z} /n_{i}}
여기서는 환이 정수환
Z
{\displaystyle \mathbb {Z} }
n
i
{\displaystyle n_{i}}
n
/
n
i
{\displaystyle n/n_{i}}
n
i
{\displaystyle n_{i}}
r
i
n
i
+
s
i
(
n
/
n
i
)
=
1
{\displaystyle r_{i}n_{i}+s_{i}(n/n_{i})=1}
r
i
,
s
i
{\displaystyle r_{i},s_{i}}
e
i
=
s
i
(
n
/
n
i
)
{\displaystyle e_{i}=s_{i}(n/n_{i})}
e
i
≡
1
(
mod
n
i
)
{\displaystyle e_{i}\equiv 1{\pmod {n_{i}}}}
e
i
≡
0
(
mod
n
j
)
{\displaystyle e_{i}\equiv 0{\pmod {n_{j}}}}
i
≠
j
{\displaystyle i\neq j}
가 성립한다.
여기에서
a
=
∑
i
a
i
e
i
{\displaystyle a=\sum _{i}a_{i}e_{i}}
i
{\displaystyle i}
a
≡
a
i
(
mod
n
i
)
{\displaystyle a\equiv a_{i}{\pmod {n_{i}}}}
a
{\displaystyle a}
이제
Z
/
n
{\displaystyle \mathbb {Z} /n}
x
,
y
{\displaystyle x,y}
x
≡
a
i
,
y
≡
a
i
(
mod
n
i
)
{\displaystyle x\equiv a_{i},y\equiv a_{i}{\pmod {n_{i}}}}
x
−
y
{\displaystyle x-y}
n
i
{\displaystyle n_{i}}
x
−
y
{\displaystyle x-y}
n
1
n
2
⋯
n
k
=
n
{\displaystyle n_{1}n_{2}\cdots n_{k}=n}
x
≡
y
(
mod
n
)
{\displaystyle x\equiv y{\pmod {n}}}
Z
/
n
{\displaystyle \mathbb {Z} /n}
이 정리는 원래 5세기 남북조 시대 의 중국 수학서 《손자산경 》(孫子算經 )에 최초로 등장하였다. 《손자산경》 하권(下卷) 문제 26번은 다음과 같다.
“
개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?
今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？
”
즉, 이는 다음과 같은 연립 합동 방정식에 관한 문제이다.
x
≡
2
(
mod
3
)
≡
3
(
mod
5
)
≡
2
(
mod
7
)
{\displaystyle x\equiv 2{\pmod {3}}\equiv 3{\pmod {5}}\equiv 2{\pmod {7}}}
이 경우, 풀이에 따라
x
≡
23
(
mod
3
⋅
5
⋅
7
=
105
)
{\displaystyle x\equiv 23{\pmod {3\cdot 5\cdot 7=105}}}
이다. 풀이에서 사용된 수는
140
≡
2
(
mod
3
)
≡
0
(
mod
5
)
≡
0
(
mod
7
)
{\displaystyle 140\equiv 2{\pmod {3}}\equiv 0{\pmod {5}}\equiv 0{\pmod {7}}}
63
≡
0
(
mod
3
)
≡
3
(
mod
5
)
≡
0
(
mod
7
)
{\displaystyle 63\equiv 0{\pmod {3}}\equiv 3{\pmod {5}}\equiv 0{\pmod {7}}}
30
≡
0
(
mod
3
)
≡
0
(
mod
5
)
≡
2
(
mod
7
)
{\displaystyle 30\equiv 0{\pmod {3}}\equiv 0{\pmod {5}}\equiv 2{\pmod {7}}}
이므로, 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.
이후 이러한 연립 합동 방정식의 문제의 해법은 1247년 남송 의 수학자 진구소 (秦九韶)가 저술한 《수서구장 》(數書九章)에서 더 일반화되었다.
