중국인의 나머지 정리[Chinese remainder theorem]

정의

중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 손자산경에 나오는 문제로 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

이를 수식으로 자세히 정리하면 아래와 같다.

서로 서로소인 음이 아닌 정수 k개가 있다고 가정하자. gcd($n_{i}, n_{j}$) = 1 (i $\neq$ j)
$n_{1}, n_{2}, ..., n_{k}$ 
$n \ = \prod_{i=1}^k n_{i}$

그렇다면 다음 연립 합동 방정식의 해 $a \in \mathbb{Z}/n$ 는 항상 유일하게 존재한다.

$a \equiv a_{1} \ (mod \ n_{1})$
$a \equiv a_{2} \ (mod \ n_{2})$
...
$a \equiv a_{k} \ (mod \ n_{k})$

 

증명

이 고대 수학 정리는 언뜻 간단해 보이지면 증명을 위해 여러 보조정리가 필요하다.

많은 글에서 보조정리를 나열하여 다루지만 이 글에서는 문제 본연의 풀이에 집중하기 위해 해의 존재성과 유일성 각각에 맞춰 풀이한다.

 

존재성

존재성은 위 연립 합동 방정식을 만족하는 해 $x \in \mathbb{Z}/n$ (쉽게 $0\leq x <n$ 인 정수) 가 존재함을 증명하면 된다. 확장된 유클리드 호제법 등 많은 정수론에서 해를 구하기 위해 혹은 존재성을 입증하기 위해 베주 항등식을 인용한다.

베주 항등식

$ a,b \in \mathbb{Z} \ (a \neq 0 \ or \ b \neq 0)$,  $gcd(a, b)=d$ 이면

$ d = au + bv $ 를 만족하는 $ u, v \in \mathbb{Z} $ 가 존재한다.

자세한 증명은 링크를 참조바라며 직관적인 이해는 아래와 같다.
최대공약수 d는 a, b의 특정 배수의 합으로 만들 수 있다는 것이다.
이를 확장한 증명으로 d는 a, b 배수 집합의 가장 작은 양의 정수다. 그리고 d의 배수들로 이 집합을 구성할 수 있다.
즉, a와 b로 나타낼 수 있는 정수 집합은 가장 기본 단위가 d라는 뜻 이다.

 

나머지 정리의 각 $n_{i}$ 에 대해 $ n_{i}, \frac{n}{n_{i}} $ 를 베주항등식 $ a, b $ 에 대입해보자.

 $n_{i}, \frac{n}{n_{i}}$ 는 서로 서로소 이므로  $gcd(n_{i}, \frac{n}{n_{i}}) = 1$

그렇다면 $n_{i}u_{i} + \frac{n}{n_{i}}v_{i} = 1$ 을 만족하는 $u_{i}, v_{i} \in  \mathbb{Z} $가 존재한다.

여기서 $e_{i} = \frac{n}{n_{i}}v_{i}$ 라고 하면 아래 두 식이 성립한다.

$e_{i} \equiv 1\ (mod\ n_{i})$
$e_{i} \equiv 0\ (mod\ n_{j},\ i \neq j)$

결국 각 $e_{i}$ 를 구하는 과정은 $mod\ n_{i}$ 시  $n_{j}\ (i \neq j)$ 에 영향을 받지 않는 값을 구하기 위함이며 이를 모두 합한 a는 위 문제 해답 중 하나이다.

$a = \sum_{i=1}^ka_{i}e_{i} $

 

유일성

증명을 위해 반례로 $ x, y \in \mathbb{Z}/n $ 두 해가 존재한다고 가정하자. 

그렇다면 모든 $n_{i}$ 에 대해 $ x \equiv y \equiv a_{i}\ (mod\ n_{i}) $ 를 만족하므로 $x-y$ 는 모든  $n_{i}$의 배수이다.

각 $ n_{i},\ n_{j}\ (i \neq j) $는 서로소라고 가정 했으므로 모든 $n_{i}$의 배수는 $n$의 배수이기도 하다.

즉, $x-y$ 는 $n$의 배수라서 $ \mathbb{Z}/n $ 에서 두 해가 존재할 수 없다.

 

응용

작업 중...

$e_{i}$ 를 구하는 방법: 유클리드 호재법 확장 vs 오일러 정리