For a better world

개요

중국인의 나머지 정리의 경우 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이며 그 기원은 다음과 같다.

중국의 5세기 문헌인 『손자산경(孫子算經)』에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

정의

$gcd(n,m) = 1$면 $\begin {cases} x \equiv b\ (mod\ n) \\ x \equiv c\ (mod\ m) \end {cases}$는 $1 \leq x \leq nm$에서 단 하나의 해를 갖는다.

증명

$x \equiv b\ (mod\ n)$    (1)

$x \equiv c\ (mod\ m)$    (2)

$x \equiv b\ (mod\ n)$이므로 $x = ny + b$를 만족하는 $y \in Z$가 존재할 것이고, 이를 (2)에 대입하면 다음과 같다.

$ny \equiv c -b\ (mod\ m)$

위 정의에 의해 위 합동식은 $1 \leq y \leq m$에서 유일한 해 $y_0$를 갖고, 따라서 $x = ny_0 + b$는 $1 \leq x \leq nm$에서 유일한 해 $x_0$를 가진다. 따라서 다음과 같다.

$x_0 = ny_0 + b$

여기서 $x_0$는 (1)의 해다. 이제 $ny_0 \equiv c -b\ (mod\ m)$에 $ny_0 = x_0 - b$를 대입하면 다음과 같다.

$x_0 \equiv c\ (mod\ m)$

$x_0$은 (2)의 해가 된다. 증명 끝.

Reference

[1] https://namu.wiki/w/중국인의%0나머지%0정리 

[2] https://freshrimpsushi.tistory.com/493