정수론

중국인의 나머지 정리

2025년 10월 19일 11:05
← 목록으로 돌아가기

1. 서론

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 정수론의 가장 아름답고 실용적인 정리 중 하나입니다. 이 정리는 3세기 중국의 수학자 손자(孫子)의 저서 『손자산경(孫子算經)』에서 처음 등장하여, "물건을 셀 때 3개씩 세면 2개가 남고, 5개씩 세면 3개가 남고, 7개씩 세면 2개가 남는다면 총 몇 개인가?" 같은 문제를 다루었습니다.

2. 합동식의 기초

정의: 합동(Congruence)

정수 $a, b$와 양의 정수 $m$에 대하여, $m$이 $a-b$를 나눌 때

$$a \equiv b \pmod{m}$$

로 표기하고, "$a$는 $b$와 모듈로 $m$에 대해 합동이다"라고 읽습니다.

이것은 $a$와 $b$를 $m$으로 나눈 나머지가 같다는 의미입니다.

3. 중국인의 나머지 정리

정리: 중국인의 나머지 정리

$m_1, m_2, \ldots, m_k$가 서로소인 양의 정수이고, $a_1, a_2, \ldots, a_k$가 임의의 정수일 때, 다음 연립 합동식

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$$

은 모듈로 $M = m_1 m_2 \cdots m_k$에 대해 유일한 해를 가집니다.

3.1 정리의 증명 (구성적 방법)

2개의 합동식인 경우를 먼저 살펴봅시다:

$$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases}$$

단계 1: $M_1 = \frac{M}{m_1} = m_2$, $M_2 = \frac{M}{m_2} = m_1$로 정의합니다.

단계 2: $\gcd(m_1, m_2) = 1$이므로, 다음을 만족하는 $y_1, y_2$가 존재합니다:

$$M_1 y_1 \equiv 1 \pmod{m_1}, \quad M_2 y_2 \equiv 1 \pmod{m_2}$$

단계 3: 해를 다음과 같이 구성합니다:

$$x = a_1 M_1 y_1 + a_2 M_2 y_2$$

검증:

3.2 일반 공식

$k$개의 합동식에 대한 일반적인 해는:

$$x = \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$$

여기서:

4. 예제

예제 1: 손자산경의 문제

다음 연립 합동식을 풀어라:

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

풀이:

1단계: $M = 3 \times 5 \times 7 = 105$

2단계: 각 $M_i$ 계산

3단계: 각 $y_i$ 계산

4단계: 해 구성

$$\begin{align} x &= 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 \\ &= 140 + 63 + 30 \\ &= 233 \equiv 23 \pmod{105} \end{align}$$

검증:

5. 연습문제

문제 1

다음 연립 합동식을 풀어라:

$$\begin{cases} x \equiv 1 \pmod{4} \\ x \equiv 2 \pmod{5} \\ x \equiv 3 \pmod{11} \end{cases}$$

풀이 1

1단계: $M = 4 \times 5 \times 11 = 220$

2단계: 각 $M_i$ 계산

3단계: 각 $y_i$ 계산

4단계: 해 구성

$$\begin{align} x &= 1 \times 55 \times 3 + 2 \times 44 \times 4 + 3 \times 20 \times 5 \\ &= 165 + 352 + 300 \\ &= 817 \equiv 157 \pmod{220} \end{align}$$

검증:

답: $x \equiv 157 \pmod{220}$

문제 2

어떤 수를 6으로 나누면 5가 남고, 7로 나누면 4가 남고, 8로 나누면 3이 남는다. 이 수 중 가장 작은 양수를 구하시오.

풀이 2

먼저 주어진 조건을 합동식으로 표현하면:

$$\begin{cases} x \equiv 5 \pmod{6} \\ x \equiv 4 \pmod{7} \\ x \equiv 3 \pmod{8} \end{cases}$$

그런데 각 조건을 관찰하면:

더 간단한 패턴을 발견할 수 있습니다. 각 경우 나머지 + 나누는 수 = 일정:

이는 $x + 1$이 6, 7, 8의 공배수임을 의미합니다.

$\text{lcm}(6, 7, 8) = 168$

따라서 $x + 1 = 168k$ (단, $k$는 양의 정수)

$x = 168k - 1$

가장 작은 양수는 $k = 1$일 때: $x = 167$

검증:

다시 계산해봅시다. CRT를 직접 적용:

주의: 6과 8은 서로소가 아니므로 ($\gcd(6,8) = 2$) 직접 적용할 수 없습니다.

먼저 처음 두 조건을 합칩시다:

$$\begin{cases} x \equiv 5 \pmod{6} \\ x \equiv 4 \pmod{7} \end{cases}$$

$M = 42$, $M_1 = 7$, $M_2 = 6$

$7y_1 \equiv 1 \pmod{6}$ → $y_1 = 1$

$6y_2 \equiv 1 \pmod{7}$ → $y_2 = 6$

$x = 5 \times 7 \times 1 + 4 \times 6 \times 6 = 35 + 144 = 179 \equiv 11 \pmod{42}$

이제 $x \equiv 11 \pmod{42}$와 $x \equiv 3 \pmod{8}$을 풀면...

$x = 42k + 11$을 $x \equiv 3 \pmod{8}$에 대입:

$42k + 11 \equiv 3 \pmod{8}$

$2k + 3 \equiv 3 \pmod{8}$

$2k \equiv 0 \pmod{8}$

$k \equiv 0 \pmod{4}$

따라서 $k = 4m$이고 $x = 42(4m) + 11 = 168m + 11$

가장 작은 양수: $x = 11$ (when $m=0$)

검증:

답: 11

6. 응용

중국인의 나머지 정리는 다음과 같은 다양한 분야에서 응용됩니다:

7. 요약

© 2025 수학 블로그. All rights reserved.