배경지식

• 모듈러 연산

1. 개요

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 **"여러 개의 제약 조건(나머지)이 있을 때, 이를 모두 만족하는 하나의 수(전체)를 찾을 수 있는가?"**라는 질문에 대한 수학적 대답이다.

고대 중국의 수학서 <손자산경(孫子算經)>에 나오는 유명한 문제에서 유래했다:

"물건이 있는데 개수는 알지 못한다. 3개씩 세면 2개가 남고, 5개씩 세면 3개가 남고, 7개씩 세면 2개가 남는다. 물건은 총 몇 개인가?"

이 문제를 현대적 수식으로 바꾸면 다음과 같은 연립 합동식이 된다:

$$ \begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases} $$

1.1 정리의 핵심 조건과 내용

이 문제를 현대적 수식으로 바꾸면 다음과 같은 연립 합동식이 된다:

$$ \begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases} $$

1.2 정리의 핵심 조건과 내용

CRT가 성립하기 위한 가장 중요한 전제 조건은 모듈러 값들이 서로소여야 한다는 것이다.

2. 정의

정수 $n_1, n_2, ..., n_k$가 쌍마다 서로소, 즉 모든 $i ≠ j$에 대해 $gcd(n_i, n_j) = 1$이라고 하자.

이때, 임의의 정수 $a_1, a_2, ..., a_k$에 대하여 다음 연립 합동식은:

$$ \begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases} $$

• 존재성 (Existence): 위 식을 만족하는 해 x가 반드시 존재한다.
• 유일성 (Uniqueness): 그 해 x는 $N = n_1 × n_2 × ... × n_k$ 법 안에서 유일하다. (즉, 일반해는 $x \equiv x_0 \pmod N$ 꼴이다.)

핵심: 각 부분의 정보(나머지)를 합치면 전체 정보(원래 수)를 완벽하게 복원할 수 있다는 뜻이다.

3. 증명

<aside> 💡

베주 항등식

a, b가 정수이고 d = gcd(a, b)일 때, ax + by = d를 만족하는 정수 x, y가 항상 존재한다

</aside>