[정수론] 6. 중국인의 나머지 정리

어렸을 때 이런 문제를 푼 기억이 있다.

"사탕 $N$개를 나눠주는데 $a$개씩 나눠주면 $m_1$개가 남고 $b$개씩 나눠주면 $m_2$개가 남을 때 사탕의 수를 구하시오."

그때는 직접 대입하거나 식을 세워서 풀었던거 같은데 중국인의 나머지정리로도 풀 수 있다.

 

중국인의 나머지 정리(Chinese Remainder Theorem)

 

>> Theorem)

$\gcd(m,n) = 1$이고 $x \equiv b \mod m$이고 $x \equiv c \mod n$이면 $x \equiv d \mod mn$인 $d$가 유일하게 존재한다.

 

proof

$x \equiv b \mod m$은 $x = my + b$로 쓸 수 있고 이를 두번째 식에 대입하면 $my + b = nz + c$가 된다.

이는 곧 $my - nz = c - b$인 디오판투스 방정식으로 나타낼 수 있고 $\gcd(m,n)=1$이기 때문에 해가 언제나 존재한다.

특수해 $y = y_0$를 구하면  일반해 $y = nk+y_0$을 얻을 수 있다.

이를 $x$에 대입하면 $x = m(nk+y_0)+b = mnk + my_0 + b (k \in \mathbb{Z})$가 되고 이는 $x \equiv my_0+b \mod mn$이 된다. $\Box$

 

여기서 드는 의문이 $\gcd(m,n) = 1$이어야 하냐는 것이다.

디오판투스 방정식을 해결할 수만 있다면 해가 나오는 것이 아닐까?

즉 $\gcd(m,n) | c-b$이기만 하면 되지 않을까?

이 경우에 디오판투스 방정식의 양 변을 $\gcd(m,n)$으로 나눌 수 있게 되므로 해는 존재 하나 그 법이 $mn$이 아니라 $\frac{mn}{\gcd(m,n)}$이 될 것이다.

 

위에서는 2개의 식에 대해서 성립한다고 설명했는데 일반화하여 $n$개의 식에 대해서도 성립한다.

즉 일반적으로는 다음과 같다.

 

>> Theorem)

$n_1, n_2, \dots, n_k$을 $i \neq j$에 대해 $\gcd(n_i, n_j) = 1$인 양의 정수라고 하면

$x \equiv a_1 \mod n_1$

$x \equiv a_2 \mod n_2$

$\dots$

$x \equiv a_k \mod n_k$

는 $n_1n_2 \dots n_k$에 대해 유일한 공통 해를 가진다.

 

proof

위의 증명을 $k-1$번 반복하면 된다. $\Box$

 

이제 백준에서 중국인의 나머지 정리를 풀 수 있게 되었다.