‘3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는?’ 이 문제는 4세기 중국의 『손자산경』에 실려 있다. 서로소인 법들에 대한 연립합동식은 항상 하나의 해를 가진다는 것이 중국인의 나머지 정리이다.
핵심 정리
$m_1,\dots,m_k$가 쌍마다 서로소이면 연립합동식
$$x\equiv a_1\pmod{m_1},\quad\dots,\quad x\equiv a_k\pmod{m_k}$$
은 법 $M=m_1m_2\cdots m_k$에 대해 단 하나의 해를 가진다.
증명 보기
존재 (해를 직접 만든다). $M_i=\frac{M}{m_i}$라 하면 $M_i$는 $m_i$와 서로소이므로 $M_iy_i\equiv1\pmod{m_i}$인 $y_i$ (역원)가 있다.
$$x=a_1M_1y_1+a_2M_2y_2+\cdots+a_kM_ky_k$$
로 두자. 법 $m_1$로 보면 $M_2,\dots,M_k$는 모두 $m_1$의 배수이므로 $x\equiv a_1M_1y_1\equiv a_1\pmod{m_1}$이다. 다른 법도 같다.
유일성. $x$, $x’$이 모두 해이면 $x-x’$은 각 $m_i$의 배수이다. $m_i$들이 쌍마다 서로소이므로 $x-x’$은 곱 $M$의 배수이고, $x\equiv x’\pmod M$이다. $\blacksquare$
그림처럼 법 $15$의 나머지 $15$개와 (법 $3$, 법 $5$) 나머지 쌍 $3\times5=15$개가 정확히 일대일로 대응한다는 것이 정리의 핵심이다.
예제 (손자산경)
$x\equiv2\pmod3$, $x\equiv3\pmod5$, $x\equiv2\pmod7$: $M=105$, $M_1=35$, $M_2=21$, $M_3=15$이다. 역원은 $35\equiv2\pmod3$에서 $y_1=2$, $21\equiv1\pmod5$에서 $y_2=1$, $15\equiv1\pmod7$에서 $y_3=1$이다.
$$x=2\cdot35\cdot2+3\cdot21\cdot1+2\cdot15\cdot1=140+63+30=233\equiv23\pmod{105}$$
확인 문제
$x\equiv1\pmod4$, $x\equiv2\pmod9$를 만족하는 가장 작은 자연수를 구하시오.
풀이 보기
$x=4k+1$을 둘째 식에 넣으면 $4k\equiv1\pmod9$이다. $4\cdot7=28\equiv1$이므로 $k\equiv7$, $x=4\cdot7+1=29$이다. 확인: $29=4\cdot7+1$, $29=9\cdot3+2$
정리
- 서로소인 법들의 연립합동식은 곱의 법에 대해 해가 하나뿐이다.
- 해는 $\sum a_iM_iy_i$로 직접 만들거나, 하나씩 대입해 구한다.
