For a better world

개요

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

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

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

정의

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

증명

$x\equiv b(modn)$    (1)

$x\equiv c(modm)$    (2)

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

$ny\equiv c-b(modm)$

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

$x_0=n{y}_0+b$

여기서 $x_0$는 (1)의 해다. 이제 $n{y}_0\equiv c-b(modm)$에 $n{y}_0=x_0-b$를 대입하면 다음과 같다.

$x_0\equiv c(modm)$

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

Reference

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

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