2014년 2월 12일에 작성한 텀블러 포스트이다.
중국인의 나머지 정리(Chinese Remainder Theorem)는 정수론의 기초 정리로서, 연립합동식 문제의 해결 방법이다. 이 정리는 중등학교의 일반 교육과정에 포함되지 않아서 일반적인 고등학생들은 그 내용을 모르는 것이 정상이다. 그런데 학교 시험에 종종 등장하여 보통의 학생들을 애먹이곤 한다. 그러면 합동 계산(Modular Arithmetic)을 모르는 학생이 연립합동식 문제를 해결할 수는 없을까? 다음 문제를 합동 계산없이 해결해보자.
서로 소인 두 양의 정수 m, n 에 대하여 m으로 나눈 나머지가 a이고, n으로 나눈 나머지가 b인 최소의 양의 정수를 구하여라.
m∙i+a = n∙j+b 을 만족하는 어떤 정수 i, j를 찾으면 충분하다. 그 이유는 다음과 같다.
x0:= m∙i+a = n∙j+b 라 할때, x0+t0∙mn ≥ 0 를 만족하는 최소의 음이 아닌 정수 t0가 존재한다. 그러면 x:= x0+t0∙mn 은 다음을 만족한다.
\[\begin{align}
x &= m( i + t_0 n) + a \\
&= n( j + t_0 m) + b
\end{align}\]
그런데 x가 최소성을 만족하는 값이 될까?
x′가 m으로 나눈 나머지가 a이고, n으로 나눈 나머지가 b인 수이면서 x 보다 작은 양의 정수라 하자. 그러면, x-x′는 m의 배수이면서 n의 배수가 되고 m과 n은 서로 소이므로 x-x′는 mn의 배수이다. 따라서, 어떤 양의 정수 t1이 존재하여 x-x′ = t1∙mn 이다.
한편, x−x0 = t0∙mn 이므로 (t0−t1)∙mn = x′-x0 이다.
이때, x0 + (t0−t1)∙mn = x0+(x′-x0) = x′ > 0 이다. 따라서 t0의 최소성에 의하여, t0-t1 ≥ t0 즉, t1 ≤ 0 이다. 이는 t1이 양의 정수라는 것에 대한 모순이다. 그러므로 x가 문제에서 구하고자 하는 값이다.
이제 m∙i+a = n∙j+b ⇔ m∙i + n∙(-j) = b-a 을 만족하는 정수 i, j를 찾는 방법을 알아보자.
m과 n은 서로 소이므로 m∙i0 + n∙j0 = 1 을 만족하는 어떤 정수 i0, j0가 존재한다.1 양변에 b-a를 곱하면, m∙i0(b-a) + n∙j0(b-a) = b-a 이 된다. 따라서 i0(b-a)를 i라 하고, -j0(b-a)를 j라 하면 충분하다.
m, n의 크기가 작다면, m∙i = n∙j + b-a 에서 우변이 m의 배수가 되도록하여 직접 i, j를 구할 수도 있다. b-a에 적당한 n의 배수를 더하거나 빼서 우변이 m의 배수가 되도록 하는 것이다.
- i0, j0는 유클리드 호제법(Euclidean Algorithm)을 이용하면 구할 수 있다. [본문으로]