중국인의 나머지 정리란?
중국인의 나머지 정리(CRT, Chinese Remainder Theorem)는 정수론의 고전적인 정리입니다. \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … 와 같은 연립 합동식에서 각 법(modulus)들이 서로소(pairwise coprime, 공통 약수가 없음)라면, \(M = m_1 \cdot m_2 \cdot \ldots\) 을 법으로 하는 유일한 해 \(x\)가 존재한다는 내용입니다. 이 계산기는 그 가장 작은 0 이상의 해를 찾아 줍니다.
계산기 사용법
각 나머지 \(a_i\)와 그에 대응하는 법 \(m_i\)를 함께 입력하세요. 두 개 또는 세 개의 합동식을 풀 수 있으며, 두 개만 필요하다면 세 번째 법은 비워 두면 됩니다. 계산기는 입력한 법들이 서로소인지 먼저 확인한 뒤 해 \(x\)와 결합된 법 \(M\)을 돌려줍니다. 임의의 정수 \(k\)에 대해 \(x + Mk\) 형태의 값은 모두 해가 됩니다.
공식 풀이
\(M = \prod_i m_i\) 라고 합시다. 각 합동식마다 \(M_i = M / m_i\) 와 \(y_i = M_i^{-1} \bmod m_i\) (확장 유클리드 호제법으로 구하는 모듈러 역원)를 정의합니다. 그러면 해는 가중합 $$x \equiv \sum_i a_i\,M_i\,y_i \pmod{M}$$ 로 표현됩니다. \(M_i\)는 \(m_i\)를 제외한 모든 법으로 나누어떨어지므로, 각 항은 자기 자신의 합동식에만 올바른 나머지를 기여합니다.
예제 풀이
\(x \equiv 2 \pmod{3}\) 와 \(x \equiv 1 \pmod{4}\) 를 풀어 봅시다. 여기서 \(M = 3 \cdot 4 = 12\) 입니다. \(M_1 = 4\) 이고 \(4 \equiv 1 \pmod{3}\) 이므로 \(y_1 = 1\); \(M_2 = 3\) 이고 \(3 \equiv 3 \pmod{4}\) 이므로 \(y_2 = 3\) (\(3 \cdot 3 = 9 \equiv 1\) 이기 때문) 입니다. 따라서 $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 입니다. 확인: \(5 \bmod 3 = 2\) ✓, \(5 \bmod 4 = 1\) ✓.
자주 묻는 질문
법들이 왜 서로소여야 하나요? 두 법이 공통 약수를 가지면, 그 최소공배수(lcm)를 법으로 할 때 해가 없거나 여러 개일 수 있어 표준 CRT 공식이 더 이상 적용되지 않습니다.
"가장 작은 0 이상의 해"란 무슨 뜻인가요? 모든 해는 \(M\)의 배수만큼 차이가 납니다. 계산기는 그중 0부터 \(M-1\) 사이에 있는 값을 알려 줍니다.
음수 나머지를 사용할 수 있나요? 네, 가능합니다. 풀이 전에 각 \(m_i\)로 나눈 나머지를 0부터 \(m_i-1\) 범위로 환산해 처리합니다.
