[Discrete Mathematics] Chinese Remainder Theorem (CRT) | 중국인의 나머지 정리

Chinese Remainder Theorem (CRT)

중국인의 나머지 정리

\(x \equiv 1\; \mathrm{(mod \; 3)},\\
x \equiv 2 \; \mathrm{(mod \; 5)},\\
x \equiv 3 \; \mathrm{(mod \; 7)}\)
을 만족하는 \(x\)를 구하는 문제에서 시작된 정리이다.
(3으로 나누었을 때 나머지가 1이고, 5로 나누었을 때 나머지가 2이며, 7로 나누었을 때 나머지가 3인 수를 구하는 문제)
- 여기서 3, 5, 7은 "쌍마다 서로소"이다.
  (3과 5는 서로소이고, 5와 7은 서로소이며, 3과 7은 서로소이다.)

- 중국인의 나머지 정리는 어떤 수를 쌍마다 서로소인 n개의 수 각각에 대해 일정한 나머지를 만족하는 수는
  그 n개의 최소공배수에 일정한 나머지를 더한 값으로 나타냄을 증명한 정리이다.

* Pairwise Coprime (쌍마다 서로소)
정수 \(n_1, n_2, \cdots n_k\) 가 \(\mathrm{gcd}(m_1, m_2, \cdots, c_k) = 1\) 을 만족하는 경우를 의미한다.


* Congruent Equation (합동방정식) (URL)

[Discrete Mathematics] Modulo Operation | 모듈로 연산

---

Definition (정의)

양의 정수 \(m_1, m_2, \cdots, m_n (n \geq 2)\) 이 Pairwise Coprime일 때,
임의의 \(c_1, c_2, \cdots, c_n\)에 대하여
아래와 같은 연립일차합동식은
유일한 \(x \equiv u \; (\mathrm{mod} \; m_1\cdot m_2\cdots m_n)\) 를 가진다.

\(\begin{cases}
x \equiv c_1 \; (\mathrm{mod} \; m_1)\\
x \equiv c_2 \; (\mathrm{mod} \; m_2)\\
\quad \vdots \\
x \equiv c_n \; (\mathrm{mod} \; m_n)
\end{cases}\)

- 즉, \(M = m_1 \cdots m_2 \cdots m_n\) 이 이들의 최소공배수일 때,
  위 연립일차합동식을 만족시키는 해 \(x\) 는 \(0\) 이상 \(M\) 미만의 정수 중에서 유일하게 존재한다.
- 각 합동식에서 x의 계수가 1이 아닌 경우가 생길 수 있는데,
  이 경우 확장 유클리드 알고리즘을 통해 Modulo에 대한 역원을 구하여 이항시킨후 CRT를 적용한다.
  (역원이 존재하지 않는 경우, 연립일차합동식의 해가 존재하지 않는다.)

---

Usage of CRT (중국인의 나머지 정리 활용 예시)

Example. Find the solution to the simultaneous congruence equation below

\begin{cases}
x \equiv 2 \; (\mathrm{mod} \; 3)\\
x \equiv 3 \; (\mathrm{mod} \; 5)\\
x \equiv 2 \; (\mathrm{mod} \; 7)\\
\end{cases}

sol)
\(3, 5, 7\)이 Pairwise Coprime이므로,
CRT에 의해 위 연립합동식은 \(\mathrm{mod} \; (3\cdot 5\cdot 7 = 105)\) 에 대해 유일한 해를 가진다.

\(m = 3\cdot 5\cdot 7 = 105\) 이라 하고,
\(a_1 = 2,\\
a_2 = 3,\\
a_3 = 2\)
라 하고,
\(n_1 = 5\cdot 7 = 35,\\
n_2 = 3\cdot 7 = 21,\\
n_3 = 3\cdot 5 = 15\) 라 하자.

\(n_1 \cdot s_1 \equiv 35s_1 \equiv 2s_1 \equiv 1 \; (\mathrm{mod} \; 3),\\
n_2 \cdot s_2 \equiv 21s_2 \equiv s_2 \equiv 1 \; (\mathrm{mod} \; 5),\\
n_3 \cdot s_3 \equiv 15s_3 \equiv s_3 \equiv 1 \; (\mathrm{mod} \; 7)\) 이고

위 합동식들을 풀면
\(s_1 = 2\\
s_2 = 1\\
s_3 = 1\)
로 도출된다.

그러므로
\(x \equiv a_1\cdot n_1\cdot s_1 + a_2\cdot n_2\cdot s_2 + a_3\cdot n_3\cdot s_3 \; (\mathrm{mod} \; m)\\
\equiv 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1 \; (\mathrm{mod} \; 105)\\
\equiv 233 \; (\mathrm{mod} \; 105)\\
\equiv 23 \; (\mathrm{mod} \; 105)\)
이다.

따라서
\(x \equiv 23 \; (\mathrm{mod} \; 105)\)
가 주어진 연립일차합동식의 유일한 해이다.

---

Reference: Wikipedia, Chinese remainder theorem (URL)
Reference: 네이버캐스트, 중국인의 나머지정리 (URL)