중국인의 나머지정리 증명하기

중국인의 나머지정리란?

양의 정수 $m_1, m_2, \cdots , m_r$가 모두 서로소이면, 임의의 $r$개의 정수 $a_1, a_2,  \cdots, a_r$에 대해 $r$개의 합동방정식

$x \equiv a_1 (\mod m_1),\ x \equiv a_2(\mod m_2) ,\ x \equiv a_r (\mod m_r)$

을 동시에 만족시키는 정수 $a$가 존재하고, $a$는 법 $m=m_1m_2 \cdots m_r$ 에 대해 유일하다.

 

증명하기

각각의 $k=1,2,3, \cdots, r$에 대해 $M_k = \frac{m}{m_k}$ 이라 하면, $m_k$는 모두 서로소이므로 $gcd(M_k,m_k) = 1$ 이다. 따라서 $M_kA_k \equiv 1 (\mod m_k)$를 만족시키는 정수 $A_k$가 존재한다. 이때 $A_k$는 $M_k$의 법 $m_k$에 대한 역수이다.

 

$a=a_1M_1A_1 + a_2M_2A_2 + \cdots + a_rM_rA_r$ 라 하자.

 

각 $k$에 대해 $h$가 $k$와 같지 않다면, $m_k \mid M_k$이므로 $a \equiv a_kM_kA_k (\mod m_k)$ 이다.

즉, $a$가 주어진 $r$개의 합동방정식의 해이다.

 

$a$가 법 $m$에 대해 유일함을 증명하기 위해 또 다른 정수 $b$가 주어진 합동식들을 모두 만족시킨다하면,

모든 $k$에 대하여 $a \equiv a_k \equiv b (\mod m_k)$이므로 $m_k \mid (a-b)$ 이다. $m_k$ 가 서로소이므로 $m = m_1m_2 \cdots m_r \mid (a-b)$ 이다. 즉, $a \equiv b (\mod m)$이다.

 

그러므로 $a$는 법 $m$에 대해 유일하다.

 

중국인의 나머지 정리 문제 예시

$x \equiv 2 (\mod 3), \ x \equiv 3 ( \mod 5) , \ x \equiv 4 (\mod 7)$을 동시에 만족시키는 정수를 모두 구하시오.

 

해답

$m_1 =3$,  $m_2 =5$,  $m_3 =7$,  $a_1 =2$,  $a_2 =3$,  $a_3 =4$ 에 대해 중국인의 나머지정리를 적용하면,

$m=105$,  $M_1=35$,  $M_2 =31$,  $M_3 =15$ 이므로

$35A_1 \equiv 1 (\mod 3)$,  $21 A_2 \equiv 1 (\mod 5)$,  $15A_3 \equiv 1 (\mod 7)$ 을 만족시키는 정수 $A_1,  A_2,  A_3$를 구해햐 한다. 이 식을 간단히 하면,

$2A_1 \equiv 1 (\mod 3)$,  $A_2 \equiv 1 (\mod 5)$,  $A_3 \equiv 1 (\mod 7)$ 이므로

$A_1 =2$,  $A_2 = 1$,  $A_3 =1$ 이다.

따라서 $a=2 \times 35 \times 2 + 3 \times 21 \times 1 + 4 \times 15 \times 1 = 263$ 이다.

 

$a \equiv 263 \equiv 53 (\mod 105)$ 이다.

 

즉, 임의의 정수 $k$에 대해 $x= 53 +105 k$ 가 위 문제를 동시에 만족시키는 모든 정수의 형태이다.