#정리
#유일성
수 $x_1$과 $x_2$가 중국인의 나머지 정리를 만족한다고 합시다. 그러면 $x_1 \equiv r_1 \pmod{a_1}$이고 $x_2 \equiv r_1 \pmod{a_1}$이므로, $x_1 - y_2$는 $a_1$로 나누어떨어집니다. 마찬가지로 $x_1 - y_2$는 $a_2$, $a_3$, 그리고 이와 같이 $a_n$까지로 나누어떨어집니다. 그런데 모든 $a_i$가 서로소이므로, $x_1 - y_1$은 이들의 곱으로 나누어떨어집니다. 그러나 그렇다면 $x_1$과 $x_2$ 중 하나는 0부터 $a_1 \cdot a_2 \cdot \ldots \cdot a_n$까지의 반열린 구간에 놓이지 않게 됩니다. 이는 모순입니다.
#존재성
$r_1$은 0부터 $a_1$까지의 반구간에, $r_2$는 0부터 $a_2$까지의 반구간에 놓이며, 나머지도 마찬가지입니다. 따라서 서로 다른 수의 조합 $r_1, r_2, \ldots r_n$의 총 개수는 정확히 $a_1 \cdot a_2 \cdot \ldots \cdot a_n$입니다. 놀랍게도 가능한 $x$의 값 역시 $a_1 \cdot a_2 \cdot \ldots \cdot a_n$개입니다. 게다가 각 $x$에 대해 중국인의 나머지 정리의 조건을 만족하는 나머지 조합 $r_1, r_2, \ldots r_n$은 많아야 하나이며, 마찬가지로 각 나머지 조합에 대해서도 $x$는 많아야 하나입니다. 이는 나머지 조합과 가능한 $x$의 값 사이에 일대일 대응이 존재한다는 뜻이며, 따라서 중국인의 나머지 정리가 증명됩니다.
#알고리즘
이미 주어진 수 $a_i$와 $r_i$의 집합에 대해 중국인의 나머지 정리의 조건을 만족하는 $x$를 찾는 것이 유용할 때가 있습니다. 이를 수행하는 알고리즘을 소개합니다.
이 알고리즘은 수학적 귀납법과 다소 비슷합니다. 먼저 $n=2$인 경우의 문제를 푸는 방법을 익히고, 그다음 큰 $n$을 더 작은 경우로 환원하는 방법을 익히겠습니다.
$n=2$일 때는 $x \equiv r_1 \pmod{a_1}$이고 $x \equiv r_2 \pmod{a_2}$인 수 $x$를 찾아야 합니다. 다르게 표현하면, $x = a_1 \cdot c_1 + r_1$이고 $x = a_2 \cdot c_2 + r_2$인 자연수 $c_1$과 $c_2$가 존재한다고 쓸 수 있습니다. 그러면 $a_1 \cdot c_2 - a_2 \cdot c_2 = r_2 - r_1$입니다. $gcd(a_1, a_2) = 1$이므로 확장 유클리드 알고리즘을 적용하여 등식이 성립하는 수 $c_1$과 $c_2$를 찾을 수 있습니다. 그리고 이를 이용하면 수 $x$를 찾을 수 있습니다.
$n$이 클 때는 다음과 같이 할 수 있습니다. 수 $a_1$과 $a_2$를 택하고, 앞 문단에서 설명한 알고리즘을 이용하여 이들에 대해 $y \equiv r_1 \pmod{a_1}$이고 $y \equiv r_2 \pmod{a_2}$인 수 $y$를 찾습니다. 이제 같은 문제를 풀되, $a_1$과 $a_2$를 $a_1 \cdot a_2$로 바꾸고, $r_1$과 $r_2$를 $y$로 바꿉니다. 다시 말해, $x \equiv y \pmod{a_1 \cdot a_2}$, $x \equiv r_3 \pmod{a_3}$, $x \equiv r_4 \pmod{a_4}$ 등을 만족하는 $x$를 찾습니다(이제 합동식이 하나 줄었습니다). 이러한 문제의 답은 원래 문제의 답으로도 적합하다는 점에 주목하십시오. 왜냐하면 $i > 2$에 대해 $x \equiv r_i \pmod{a_i}$는 정의에 의해 성립하고, $x \equiv y \pmod{a_1 \cdot a_2}$, $y \equiv r_1 \pmod{a_1}$, $y \equiv r_2 \pmod{a_2}$이므로 $x \equiv r_1 \pmod{a_1}$이고 $x \equiv r_2 \pmod{a_2}$이기 때문입니다. 이렇게 하여 문제를 더 작은 문제로 환원하는 방법을 익혔습니다.
{{ Утверждение |Утверждение=위에서 설명한 알고리즘의 실행 시간은 $O(n \log C)$입니다. 여기서 $C$는 모든 $a_i$의 곱에 대한 상한입니다. |Доказательство=연습 문제로 남깁니다. }}