[정수론] 중국인의 나머지 정리 풀이 방법 정리

 

중국인의 나머지 정리 풀이 방법 정리

정수론을 공부하다 보면 연립합동식(동시에 만족해야 하는 나머지 조건)을 풀어야 하는 경우가 자주 나옵니다.  중국인의 나머지 정리(Chinese Remainder Theorem, CRT)를 이용하면 간단히 풀 수 있습니다. 

---

1. 중국인의 나머지 정리란?

다음과 같은 연립합동식이 있다고 합시다.

$$
\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}
$$

여기서 법(modulus) $m_1, m_2, \dots, m_k$가 서로소(즉, $\gcd(m_i, m_j) = 1$)라면, 이 연립합동식은 항상 해를 가지며, 그 해는 전체 법

$$
M = m_1 \cdot m_2 \cdot \cdots \cdot m_k
$$

에서 유일하게 결정됩니다.

---

2. 풀이 절차

중국인의 나머지 정리를 푸는 과정은 다음과 같습니다.

전체 법 $M$ 구하기
모든 법을 곱합니다.

$$
M = m_1 \cdot m_2 \cdot \cdots \cdot m_k
$$

부분 곱 $M_i$ 구하기

$$
M_i = \frac{M}{m_i}
$$

역원 $y_i$ 구하기를 만족하는 $y_i$를 찾습니다. (확장 유클리드 알고리즘으로 계산)

$$
M_i \cdot y_i \equiv 1 \pmod{m_i}
$$

최종 해 $x$ 구하기

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

---

3. 예제 풀이

문제:

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

(1) 전체 법

$$
M = 3 \cdot 5 \cdot 7 = 105
$$

(2) 부분 곱

$$
M_1 = 105 / 3 = 35, \quad M_2 = 105 / 5 = 21, \quad M_3 = 105 / 7 = 15
$$

(3) 역원 찾기

• $35y_1 \equiv 1 \pmod{3} \implies y_1 = 2$
• $21y_2 \equiv 1 \pmod{5} \implies y_2 = 1$
• $15y_3 \equiv 1 \pmod{7} \implies y_3 = 1$

(4) 해 구하기

$$
x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105}
$$

$$
x \equiv 140 + 63 + 30 = 233 \pmod{105}
$$

$$
x \equiv 23 \pmod{105}
$$

✅ 따라서 해는

$$
x = 23 + 105k \quad (k \in \mathbb{Z})
$$

---

4. 정리

• 중국인의 나머지 정리는 서로소 법을 가진 연립합동식을 풀 수 있는 강력한 도구
• 전체 법 $M$을 구하고, 각 부분 곱 $M_i$와 역원 $y_i$를 찾으면 된다.
• 최종 해는 $x \equiv \sum a_i M_i y_i \pmod{M}$ 꼴로 계산된다.
• 암호학, 알고리즘, 수학 올림피아드 등 다양한 분야에서 필수적으로 활용된다.

 

함께 보면 좋은 글

 

[수학경시대회] 배수판정법

 

[수학경시] 평균속도 조화평균으로 쉽게 구하기