III. 합동 · 5/16

중국인의 나머지 정리

연립 합동식, CRT와 그 응용

읽음 0/0 갱신 2026-06-30

개요 — 동기·문제의식

"3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는 수는?" — 이런 연립 합동식은 1700년 전 중국 산학서에 이미 등장한다.³ 언뜻 보면 세 조건을 동시에 만족하는 수가 존재한다는 보장조차 없어 보이지만, 법(modulus)들이 쌍마다 서로소이기만 하면 답은 항상 존재하고, 더 큰 법을 기준으로 유일하다. 이것이 중국인의 나머지 정리(CRT)다.

CRT가 중요한 이유는 단순한 퍼즐 풀이를 넘어선다. 그것은 "큰 법 $\bmod\, mn$ 에서의 계산"을 "작은 법 $\bmod\, m$, $\bmod\, n$ 에서의 계산 두 개"로 쪼개도 정보 손실이 없다는 구조적 사실이다. 이 분해 가능성이 Euler $\varphi$ 함수의 곱셈성(오일러 φ 함수와 정리)을 증명하는 핵심 도구이고, RSA 복호화를 4배 가까이 가속하는 실용적 트릭(모듈러 거듭제곱과 RSA)이며, 대수적으로는 환의 동형 $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ 이라는 명제다.

직관

법이 서로소라는 조건은 "두 시계가 서로 다른 속도로 돌아간다"는 그림으로 이해하면 좋다. $\bmod\,3$ 시계는 눈금이 3개, $\bmod\,5$ 시계는 눈금이 5개다. $x$가 1씩 늘어나면 두 시계 바늘이 동시에 한 칸씩 움직이는데, 두 시계의 눈금 수가 서로소($\gcd(3,5)=1$)이면 두 바늘의 조합 $(x\bmod3,\,x\bmod5)$ 은 $x=0,1,\dots,14$ 동안 15가지를 전부 한 번씩 거친 뒤에야 처음 조합으로 되돌아온다. 즉 $(x\bmod3, x\bmod5)$ 라는 한 쌍의 정보가 $x\bmod15$ 라는 정보와 완전히 동등하다 — 정보를 잃지도, 중복되지도 않는다. 법이 서로소가 아니면(예: 6과 4) 두 바늘이 모든 조합을 다 거치지 못하고 일부만 반복하므로 이 일대일 대응이 깨진다. CRT는 이 "정보량이 보존되는 분해"를 정리로 만든 것이다.

정의

(중국인의 나머지 정리, 일반형) $m_1,m_2,\dots,m_k$ 가 쌍마다 서로소($i\ne j$ 이면 $\gcd(m_i,m_j)=1$)이고 $a_1,\dots,a_k$ 가 임의의 정수이면, 연립 합동식¹ $$x\equiv a_1\pmod{m_1},\quad x\equiv a_2\pmod{m_2},\quad\dots,\quad x\equiv a_k\pmod{m_k}$$ 은 $M=m_1m_2\cdots m_k$ 를 법으로 유일한 해 $x\in\{0,1,\dots,M-1\}$ 을 가진다(즉 모든 정수해는 $\bmod\,M$ 으로 합동).

기호	의미
$M=m_1\cdots m_k$	전체 법(법들의 곱)
$M_i=M/m_i$	$i$번째를 제외한 나머지 법들의 곱 — $\gcd(M_i,m_i)=1$
$y_i$	$M_iy_i\equiv1\pmod{m_i}$ 의 해 (확장 유클리드 호제법으로 구함)

구성적 증명 (해 공식). 각 $i$에 대해 $M_i=M/m_i$ 는 $m_i$ 와 서로소이므로(나눗셈과 최대공약수) 역원 $y_i$ 가 존재: $M_iy_i\equiv1\pmod{m_i}$. 그러면 $$x\equiv\sum_{i=1}^k a_iM_iy_i\pmod M$$ 이 해가 된다. 왜냐하면 $j\ne i$ 이면 $m_j\mid M_i$ 이므로 항 $a_jM_jy_j$ 는 $\bmod\,m_i$ 로 $0$이 되고, 자기 항만 $a_iM_iy_i\equiv a_i\cdot1=a_i\pmod{m_i}$ 으로 살아남는다 — 정확히 원하는 합동을 모든 $i$ 에서 동시에 만족시킨다.

유일성의 증명. $x,x'$ 이 둘 다 해라면 모든 $i$ 에서 $x\equiv x'\pmod{m_i}$, 즉 $m_i\mid(x-x')$. $m_i$ 들이 쌍마다 서로소이므로 그 곱 $M$ 도 $(x-x')$ 을 나눈다(나눗셈과 최대공약수의 최소공배수 성질) → $x\equiv x'\pmod M$.

왜 "쌍마다 서로소"가 필요한가. 만약 $m_1,m_2$ 가 공약수 $d>1$ 을 가지면, $a_1\not\equiv a_2\pmod d$ 인 경우 두 합동식이 모순되어 해가 아예 없다(아래 예제 4). 서로소 조건은 이런 충돌이 원천적으로 불가능함을 보장한다.

주요 정리

정리 (환 동형으로서의 CRT). $\gcd(m,n)=1$ 이면 사상 $x\bmod mn \mapsto (x\bmod m,\, x\bmod n)$ 은 환의 동형 $$\mathbb{Z}_{mn}\ \cong\ \mathbb{Z}_m\times\mathbb{Z}_n$$ 을 정의한다. 증명 스케치. 위 해의 존재성·유일성이 바로 이 사상이 전단사임을 말한다; 덧셈·곱셈을 좌표별로 보존하는 것은 합동의 정의에서 바로 나온다.

따름정리 (가역원의 곱셈성, φ의 곱셈성). 위 동형은 가역원들의 군으로 제한된다: $\mathbb{Z}_{mn}^\times\cong\mathbb{Z}_m^\times\times\mathbb{Z}_n^\times$ ($x$가 $mn$과 서로소 $\iff$ $x\bmod m$이 $m$과, $x\bmod n$이 $n$과 각각 서로소). 양변의 원소 개수를 세면² $$\varphi(mn)=\varphi(m)\varphi(n)\qquad(\gcd(m,n)=1)$$ — 오일러 φ 함수와 정리에서 쓰는 φ의 곱셈성이 정확히 이 따름정리다.

정리 (세 개 이상 모듈러스로의 확장). 두 모듈러스 버전을 귀납적으로 적용하면 임의의 개수 $k$ 의 쌍마다 서로소인 법에 대해서도 성립한다: $m_1,m_2$ 를 먼저 합쳐 법 $m_1m_2$ 의 단일 합동식으로 만들고, 그 결과를 $m_3$ 과 다시 합치는 식으로 반복한다(아래 예제 1이 이 방법을 보여준다).

예제

예제 1 (고전 삼중 연립, 단계적 결합). $x\equiv2\pmod3,\ x\equiv3\pmod5,\ x\equiv2\pmod7$ 을 풀자.

1단계 (3과 5 결합). $x\equiv2\pmod3,\ x\equiv3\pmod5$. $M=15$, $M_1=5$, $M_2=3$. $5y_1\equiv1\pmod3\Rightarrow2y_1\equiv1\pmod3\Rightarrow y_1=2$; $3y_2\equiv1\pmod5\Rightarrow y_2=2$. $x\equiv2\cdot5\cdot2+3\cdot3\cdot2=20+18=38\equiv8\pmod{15}$.

2단계 (결과와 7 결합). $x\equiv8\pmod{15},\ x\equiv2\pmod7$. $M=105$, $M_1=7$, $M_2=15$. $7y_1\equiv1\pmod{15}\Rightarrow y_1=13$ ($7\cdot13=91=6\cdot15+1$); $15y_2\equiv1\pmod7\Rightarrow y_2\equiv1\pmod7$ ($15\equiv1$, 자기 역원). $x\equiv8\cdot7\cdot13+2\cdot15\cdot1=728+30=758\equiv758-7\cdot105=758-735=23\pmod{105}$.

검산. $23=3\cdot7+2$ ✓, $23=5\cdot4+3$ ✓, $23=7\cdot3+2$ ✓.

예제 2 (직접 공식으로 두 식). $x\equiv1\pmod4,\ x\equiv2\pmod9$. $M=36$, $M_1=9$, $M_2=4$. $9y_1\equiv1\pmod4\Rightarrow y_1\equiv1\pmod4$ ($9\equiv1$이므로 $y_1=1$); $4y_2\equiv1\pmod9\Rightarrow y_2=7$ ($4\cdot7=28\equiv1\pmod9$). $x\equiv1\cdot9\cdot1+2\cdot4\cdot7=9+56=65\equiv65-36=29\pmod{36}$.

검산. $29=4\cdot7+1$ ✓, $29=9\cdot3+2$ ✓.

예제 3 (φ 곱셈성 응용). $\varphi(15)$ 를 CRT의 따름정리로 계산: $\varphi(15)=\varphi(3)\varphi(5)=2\cdot4=8$. 직접 세어 확인: $1,\dots,15$ 중 $3,5$ 와 서로소인 것 $\{1,2,4,7,8,11,13,14\}$ — 정확히 8개. ✓

예제 4 (서로소가 아니면 해가 없을 수 있다). $x\equiv0\pmod2,\ x\equiv1\pmod4$ 는 해가 없다 — 첫 식은 $x$가 짝수, 둘째 식은 $x=4k+1$ (홀수)을 강제하므로 모순. $\gcd(2,4)=2\ne1$ 이라 정리의 가설이 깨졌다.

예제 5 (해가 있는 비서로소 경우, 정리 밖의 보너스). $x\equiv2\pmod4,\ x\equiv2\pmod6$ 은 법이 서로소가 아니지만($\gcd=2$) 두 식이 공통 법 $2$ 에서 일치($2\equiv2\pmod2$)하므로 해가 존재: $x\equiv2\pmod{12}$ ($\mathrm{lcm}(4,6)=12$). 단, 이는 CRT의 보장 범위 밖이라 매번 일치 여부를 직접 확인해야 한다.

예제 6 (RSA-CRT 가속, 개념 예고). $N=pq$ 인 RSA에서 $c^d\bmod N$ 을 직접 계산하는 대신, $c^d\bmod p$ 와 $c^d\bmod q$ 를 각각 (지수를 $p-1$, $q-1$ 로 줄여서) 계산한 뒤 CRT로 합치면 — 작은 법에서의 거듭제곱이 훨씬 빠르므로 — 전체 복호화가 약 4배 빨라진다. 구체적 수치 예는 모듈러 거듭제곱과 RSA 참조.

흔한 오해와 함정

"법이 아무거나면 된다" — 틀림. 쌍마다 서로소가 필수 가설이다. 두 법이 공약수를 가지면 해가 아예 없을 수도(예제 4), 우연히 있을 수도(예제 5) 있어 정리가 보장하는 깔끔한 유일해 구조가 깨진다.
"유일한 해 = 정수 하나" — 정확히는 $\bmod\,M$ 으로 유일하다. 실제 정수해는 $x_0, x_0\pm M, x_0\pm2M,\dots$ 무한히 많고, "유일"은 이들이 전부 한 잉여류라는 뜻이다.
역원 계산 생략 — $M_iy_i\equiv1\pmod{m_i}$ 의 $y_i$ 를 "느낌"으로 때려 맞히면 안 된다. 작은 법에서는 시행착오로도 찾을 수 있지만 일반적으로는 확장 유클리드 호제법이 정석이다.
삼중 이상을 한 번에 공식 적용하려다 실수 — $k\ge3$ 일 때는 두 식씩 묶어 단계적으로 줄이는 편이 계산 실수를 줄인다(예제 1).
계수 곱 $a_iM_iy_i$ 를 $m_i$ 가 아니라 $M$ 으로 줄이지 않고 헷갈림 — 각 항은 자기 법 $m_i$ 에서만 $a_i$ 와 합동임을 보장하므로, 최종 합산 후 반드시 $\bmod\,M$ 으로 환원해야 한다.

큰 그림 / 연결

CRT는 정수론 전체에서 "큰 문제를 서로소 조각으로 쪼개 풀고 다시 합친다"는 전략의 원형이다. 가장 직접적인 따름정리는 오일러 φ 함수와 정리의 곱셈성 $\varphi(mn)=\varphi(m)\varphi(n)$ 이고, 이는 수론적 함수에서 다루는 다른 곱셈적 함수($\tau$, $\sigma$)들의 소수거듭제곱 공식과 같은 패턴을 공유한다. 계산 정수론에서는 모듈러 거듭제곱과 RSA의 RSA-CRT 가속과, 더 일반적으로 큰 법에서의 모듈러 연산을 작은 소수 법들로 쪼개 병렬 계산하는 기법(다항식 보간·FFT 기반 정수 곱셈)의 토대가 된다. 대수학에서는 $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ 라는 환 동형이 algebra 위키의 환의 직적(direct product of rings) 개념의 가장 구체적인 사례이며, 이 패턴은 일반적인 가환환의 중국인의 나머지 정리(이데알의 곱과 교집합이 서로소일 때)로 추상화된다.

연습문제

$x\equiv1\pmod5,\ x\equiv2\pmod6,\ x\equiv3\pmod7$ 을 풀어라.
CRT 해 공식으로 $x\equiv3\pmod4,\ x\equiv4\pmod5$ 를 풀어라.
CRT를 이용해 $\varphi(72)$ 를 계산하라.
$x\equiv5\pmod6,\ x\equiv3\pmod{10}$ 의 해가 존재하는지 (법이 서로소가 아님에 주의해) 판정하라.
$\mathbb{Z}_{12}^\times\cong\mathbb{Z}_4^\times\times\mathbb{Z}_3^\times$ 에서 원소 $5,7,11$ 의 대응 쌍을 모두 구하라.
$x\equiv2\pmod3,\ x\equiv1\pmod4,\ x\equiv3\pmod5$ 를 단계적 결합으로 풀어라.
$100$ 이하의 자연수 중 $3$으로 나누면 $1$, $4$로 나누면 $2$, $5$로 나누면 $4$가 남는 수를 모두 구하라.
RSA에서 $N=33=3\cdot11$ 일 때, $c^{17}\bmod 3$ 과 $c^{17}\bmod 11$ 을 각각 구해 CRT로 $c^{17}\bmod 33$ 을 합치는 과정을 $c=5$ 로 시연하라.

힌트 / 정답

$M=210$. $5,6$ 결합: $x\equiv1\pmod5,\,x\equiv2\pmod6\Rightarrow M=30$, $6y_1\equiv1\pmod5\Rightarrow y_1=1$, $5y_2\equiv1\pmod6\Rightarrow y_2=5$, $x\equiv1\cdot6\cdot1+2\cdot5\cdot5=6+50=56\equiv26\pmod{30}$. 이어서 $26,30$ 과 $7$ 결합: $x\equiv26\pmod{30},x\equiv3\pmod7\Rightarrow$ $30y_2\equiv1\pmod7\Rightarrow2y_2\equiv1\Rightarrow y_2=4$; $7y_1\equiv1\pmod{30}\Rightarrow y_1=13$ ($7\cdot13=91=3\cdot30+1$); $x\equiv26\cdot7\cdot13+3\cdot30\cdot4=2366+360=2726\equiv2726-12\cdot210=2726-2520=206\pmod{210}$. 검산: $206=5\cdot41+1,\ 6\cdot34+2,\ 7\cdot29+3$ 모두 ✓.
$M=20$, $5y_1\equiv1\pmod4\Rightarrow y_1=1$, $4y_2\equiv1\pmod5\Rightarrow y_2=4$ → $x\equiv3\cdot5\cdot1+4\cdot4\cdot4=15+64=79\equiv19\pmod{20}$. 검산: $19=4\cdot4+3,\ 5\cdot3+4$ ✓.
$72=8\cdot9$, $\gcd(8,9)=1$ → $\varphi(72)=\varphi(8)\varphi(9)=4\cdot6=24$.
$\gcd(6,10)=2$. $5\bmod2=1$, $3\bmod2=1$ — 일치하므로 해 존재(CRT 보장 밖이지만 우연히 성립): $\mathrm{lcm}(6,10)=30$, 직접 탐색하면 $x=23$ ($23=6\cdot3+5,\ 23=10\cdot2+3$) → $x\equiv23\pmod{30}$.
$\mathbb{Z}_{12}^\times=\{1,5,7,11\}$. $5\mapsto(5\bmod4,5\bmod3)=(1,2)$; $7\mapsto(3,1)$; $11\mapsto(3,2)$.
$3,4$ 결합($M=12$): $x\equiv2\pmod3,x\equiv1\pmod4$ → $4y_1\equiv1\pmod3\Rightarrow y_1=1$, $3y_2\equiv1\pmod4\Rightarrow y_2=3$, $x\equiv2\cdot4\cdot1+1\cdot3\cdot3=8+9=17\equiv5\pmod{12}$. 이어서 $5,12$ 와 $5$($\bmod5$) 결합: $x\equiv5\pmod{12},x\equiv3\pmod5$ → $12y_2\equiv1\pmod5\Rightarrow2y_2\equiv1\Rightarrow y_2=3$; $5y_1\equiv1\pmod{12}\Rightarrow y_1=5$ ($5\cdot5=25\equiv1$); $x\equiv5\cdot5\cdot5+3\cdot12\cdot3=125+108=233\equiv233-3\cdot60=53\pmod{60}$. 검산: $53=3\cdot17+2,\ 4\cdot13+1,\ 5\cdot10+3$ ✓.
위 예제1과 동일한 연립식 변형: $x\equiv1\pmod3,x\equiv2\pmod4,x\equiv4\pmod5$. $M=60$. $3,4$ 결합: $x\equiv1\pmod3,x\equiv2\pmod4$ → $4y_1\equiv1\pmod3\Rightarrow y_1=1$, $3y_2\equiv1\pmod4\Rightarrow y_2=3$, $x\equiv1\cdot4\cdot1+2\cdot3\cdot3=4+18=22\equiv10\pmod{12}$. $10,12$ 와 $5$ 결합: $12y_2\equiv1\pmod5\Rightarrow2y_2\equiv1\Rightarrow y_2=3$; $5y_1\equiv1\pmod{12}\Rightarrow y_1=5$; $x\equiv10\cdot5\cdot5+4\cdot12\cdot3=250+144=394\equiv394-6\cdot60=34\pmod{60}$. $100$ 이하 해: $34, 94$.
$c=5$: $\bmod3$, $5\equiv2$, $\varphi(3)=2$이므로 $2^{17}=2^{16}\cdot2\equiv1\cdot2=2\pmod3$ (Fermat). $\bmod11$, $\varphi(11)=10$, $17\equiv7\pmod{10}$이므로 $5^{17}\equiv5^7\pmod{11}$: $5^2=25\equiv3,\,5^4\equiv9,\,5^7=5^4\cdot5^2\cdot5\equiv9\cdot3\cdot5=135\equiv135-12\cdot11=3\pmod{11}$. CRT로 합치기: $x\equiv2\pmod3,x\equiv3\pmod{11}$, $M=33$, $11y_1\equiv1\pmod3\Rightarrow2y_1\equiv1\Rightarrow y_1=2$, $3y_2\equiv1\pmod{11}\Rightarrow y_2=4$ ($3\cdot4=12\equiv1$); $x\equiv2\cdot11\cdot2+3\cdot3\cdot4=44+36=80\equiv80-2\cdot33=14\pmod{33}$. 직접 검산: $5^{17}\bmod33$을 연속제곱으로 — $5^2=25,\,5^4=625\equiv625-18\cdot33=625-594=31\equiv-2,\,5^8\equiv4,\,5^{16}\equiv16,\,5^{17}=5^{16}\cdot5\equiv16\cdot5=80\equiv14\pmod{33}$ ✓ 일치.