중국인의 나머지 정리 증명
정리
$\gcd(n,m) = 1$ 면 $\begin{cases} x \equiv b \pmod{n} \\ x \equiv c \pmod{m} \end{cases}$ 는 $1 \le x \le nm$ 에서 단 하나의 해를 갖는다.
설명
중국에서 서기 3세기에서 5세기에 쓰여졌다고 전해지는 한 수학서에는 이런 문제가 있었다고 한다.
어떤 수를 셋 씩 짝 지으면 둘이 남고, 다섯 씩 짝 지으면 셋이 남고, 일곱 씩 짝 지으면 둘이 남는다. 이 수는 무엇인가? - 손자산경 하권, 연습문제 26번
이를 현대적인 수학의 표현을 쓰면 $$ \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases} $$ 의 해를 구하는 문제가 된다. 지금에 와서 이 문제를 푸는데 쓰이는 정리는 ‘중국인의 나머지 정리’ 라고 알려져 있다.동서고금을 막론하고 연립 합동 방정식의 풀이에 대한 가장 오래된 기록이 중국의 수학책에서 소개되었기 때문이다.
참고로 손자산경의 저자는 그저 손씨라는 것만 알려져 있으며, ‘손자병볍’을 쓴 ‘손무’와는 전혀 관계가 없다.
예시에도 보았듯 당연한 사실이지만, 주어진 식은 두 개 이상이 되더라도 전혀 상관이 없다.
증명
전략: 구체적으로 유일한 해를 구한다.
$$ \begin{equation} x \equiv b \pmod{n} \end{equation} $$ $$ \begin{equation} x \equiv c \pmod{m} \end{equation} $$ $x \equiv b \pmod{n}$ 이므로 $x = ny + b$ 를 만족하는 $y \in \mathbb{Z}$ 가 존재할 것이고, 이를 $(2)$ 에 대입하면 $$ ny \equiv c - b \pmod{m} $$ 한편 위 합동식은 $ 1 \le y \le m$ 에서 유일한 해 $y_{0}$ 을 갖고, 따라서 $x = ny_{0} + b$ 는 $ 1 \le x \le nm$ 에서 유일한 해 $x_{0}$ 를 갖는다. 따라서 $$ x_{0} = ny_{0} + b $$ 여기서 $x_{0}$ 는 $(1)$ 의 해다. 이제 $ny_{0} \equiv c - b \pmod{m}$ 에 $ny_{0} = x_{0} - b$ 를 대입하면 $$ x_{0} \equiv c \pmod{m} $$ 다시 말해, $x_{0}$ 은 $(2)$ 의 해가 됨을 확인할 수 있다.
■
코드
다음 코드는 중국인의 나머지 정리를 R 언어로 구현한 것이다. $n \times 2$ 사이즈의 행렬을 주면 해를 구해준다. 예제와 마찬가지로 주어진 문제가 $\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$ 이라면 행렬 $S := \begin{bmatrix} 2 & 3 \\ 3 & 5 \\ 2 & 7 \end{bmatrix}$ 을 넣으면 된다.
CRA<-function(S) #Algorithm of chinese remainder theorem
{
r<-S[,1] # matrix S express below sysyem.
mod<-S[,2] # x = r[1] (mod mod[1])
n<-length(r) # x = r[2] (mod mod[2])
# x = r[3] (mod mod[3])
A<-seq(r[1],to=mod[1]*mod[2],by=mod[1])
for(i in 2:n)
{
B=seq(r[i],to=mod[1]*mod[i],by=mod[i])
r[1]=min(A[A %in% B])
mod[1]=mod[1]*mod[i]
if (i<n) {A=seq(r[1],to=mod[1]*mod[i+1],by=mod[1])}
}
return(r[1])
}
example<-matrix(c(2,3,3,5,2,7),ncol=2,byrow=T); example
CRA(example)
위 코드를 실행시킨 결과는 다음과 같다. $x=23$ 이 주어진 문제의 답이 됨을 확인해보자.
