예제
다음 일차연립합동식을 만족하는 모든 $x$를 구하시오.
\begin{aligned}
x &\equiv 5 \pmod{7} \\
x &\equiv 13 \pmod{18} \\
x &\equiv 21 \pmod{29}
\end{aligned}
$x$가 첫 번째 식을 만족해야 하므로 $x=7n+5$라고 쓸 수 있습니다. 이를 두 번째 식에 대입하면
\[ 7n + 5 \equiv 13 \pmod{18} \qquad \Rightarrow \qquad 7n \equiv 8 \pmod{18} \]
법 18에 대한 7의 곱셈 역원 13을 양변에 곱합시다. 7과 18이 서로소이므로 존재합니다.
\[ n \equiv 14 \pmod{18} \]
따라서 $n=18m+14$로 나타낼 수 있고, 이걸 다시 $x=7n+5$에 대입하면 $x=126m+103$, 또는
\begin{equation} x \equiv 103 \pmod{126} \label{eq:merged} \end{equation}
식 \eqref{eq:merged}은 연립합동식의 첫 번째와 두 번째 식을 합친 것입니다. 같은 방법으로 세 번째 식까지 합치면 연립합동식의 해를 구할 수 있습니다. $x=126m+103$을 세 번째 식에 대입하면
\[
126m + 103 \equiv 21 \pmod{29} \qquad\Rightarrow\qquad
126m \equiv 5 \pmod{29}
\]
역시 법 29에 대한 126의 곱셈 역원 3을 곱하여 $m$을 구합니다.
\[ m \equiv 15 \pmod{29} \]
고로 $m=29k+15$이고, $x=126m+103$에 대입하면 주어진 방정식의 해는 다음과 같습니다.
\[ x \equiv 1993 \pmod{3654} \]
중국인의 나머지 정리
위 문제를 푸는 핵심 아이디어는, 법 둘을 어떻게 고르든 항상 서로소라는 걸 이용해서 곱셈 역원을 구하고 두 합동식을 하나로 합친다는 겁니다. 이를 일반화하여 $m_1$, $\cdots$, $m_n$이
\[ \gcd(m_i, m_j) = 1 \qquad \text{for } \ i\neq j \]
를 만족할 때, 일차연립합동식
\begin{gathered}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_n \pmod{m_n}
\end{gathered}
의 해를 구하는 일반적인 알고리즘을 생각할 수 있습니다. 이를 유도하기 전에 유도 과정에 필요한 보조정리 두 가지를 짚고 넘어가겠습니다.
정수 $a$, $b$, $k$에 대해
\[ 1 - ka\left[(ka)^{-1}\bmod{b}\right] = b(b^{-1}\bmod{a}) \]
단, $a^{-1}\bmod{m}$은 법 $m$에 대한 $a$의 곱셈 역원을 의미한다.
곱셈 역원의 정의에 의해 적당한 정수 $l$이 존재하여,
\[ ka\left[(ka)^{-1}\bmod{b}\right] = bl + 1 \]
또는 법 $a$에 대한 합동식으로 쓰면
\[ bl + 1 \equiv 0 \pmod{a} \qquad\Rightarrow\qquad b(-l) \equiv 1 \pmod{a} \]
이므로 $-l$은 법 $a$에 대한 $b$의 곱셈 역원입니다. 따라서
\[ 1 - ka\left[(ka)^{-1}\bmod{b}\right] = b(-l) = b(b^{-1}\bmod{a}) \]
가 성립합니다.
정수 $a$, $b$, $m$에 대해
\[ (a^{-1}\bmod{m})(b^{-1}\bmod{m}) = (ab)^{-1}\bmod{m} \]
\begin{gather*}
\begin{aligned}
a(a^{-1}\bmod{m}) &\equiv 1 \pmod{m} \\
b(b^{-1}\bmod{m}) &\equiv 1 \pmod{m}
\end{aligned} \\
\Rightarrow\ ab(a^{-1}\bmod{m})(b^{-1}\bmod{m}) \equiv 1 \pmod{m}
\end{gather*}
따라서 보조정리가 성립합니다.
제일 처음 두 식부터 합쳐봅시다. $x=m_1k_1+a_1$이라 하고 둘째 식에 대입하면
\begin{align*}
&m_1k_1 + a_1 \equiv a_2 \pmod{m_2} \\
\Rightarrow\ & k_1 \equiv (m_1^{-1} \bmod{m_2})(a_2-a_1) \pmod{m_2} \\
\Rightarrow\ & k_1 = m_2k_2 + (m_1^{-1} \bmod{m_2})(a_2-a_1) \\
\end{align*}
\begin{align*}
\therefore x
&= m_1m_2k_2 + m_1(m_1^{-1}\bmod{m_2})(a_2-a_1) + a_1 \\
&= m_1m_2k_2 + \left[ 1 - m_1(m_1^{-1}\bmod{m_2}) \right]a_1 + m_1(m_1^{-1}\bmod{m_2})a_2 \\
&= m_1m_2k_2 + m_2(m_2^{-1}\bmod{m_1})a_1 + m_1(m_1^{-1}\bmod{m_2})a_2
\end{align*}
그대로 셋째 식에 또 대입합시다. 중간 과정이 매우 긴데, 결과만 적겠습니다.
\begin{align*}
x =& m_1m_2m_3k_3 + m_2m_3\left[(m_2m_3)^{-1}\bmod{m_1}\right]a_1 \\
&\quad+ m_3m_1\left[(m_3m_1)^{-1}\bmod{m_2}\right]a_2 + m_1m_2\left[(m_1m_2)^{-1}\bmod{m_3}\right]a_3
\end{align*}
규칙이 보이시나요? $M=m_1m_2\cdots m_3$, $M_i=M/m_i$라 하면 연립합동식의 최종 정답은 아래와 같습니다.
\[ x \equiv \sum_{i=1}^n M_i(M_i^{-1}\bmod{m_i})a_i \pmod{M} \]
이를 중국인의 나머지 정리(chinese remainder theorem, CRT)라고 합니다. 예제 1을 중국인의 나머지 정리로 풀어봅시다.
\begin{gather*}
M = 3654 \\
M_1 = 522, \qquad M_2 = 203, \qquad M_3 = 126 \\
M_1^{-1}\bmod{m_1} = 2, \qquad M_2^{-1}\bmod{m_2} = 11, \qquad M_3^{-1}\bmod{m_3} = 3 \\
\therefore x \equiv 522\times2\times5 + 203\times11\times13 + 126\times3\times21 \equiv 1993 \pmod{3654}
\end{gather*}
법이 서로소가 아닐 때
일차연립합동식에서 법이 서로소가 아니어도 두 식을 합칠 수 있습니다. $m_1$과 $m_2$가 서로소가 아니라고 가정하고 다음 합동식을 봅시다.
\begin{equation} \begin{aligned}
x &\equiv a_1 \pmod{m_1} \\
x &\equiv a_2 \pmod{m_2}
\end{aligned} \label{eq:not-coprime} \end{equation}
똑같은 방식으로 $x=m_1k_1+a_1$이라 하고 두 번째 식에 대입하면
\[ m_1k_1 \equiv a_2 - a_1 \pmod{m_2} \qquad\Rightarrow\qquad m_1k_1 + m_2k_2 = a_2 - a_1 \]
만약 $a_2 - a_1$이 $m_1$과 $m_2$의 최대공약수 $g$의 배수가 아니라면 식 \eqref{eq:not-coprime}의 해는 존재하지 않습니다. 이제 확장 유클리드 호제법으로 적당한 $k_1$의 값을 하나 구했다고 하면($k_0$라고 합시다) $k_1$의 일반해는
\[ k_1 = k_0 + l \frac{m_2}{g} \]
따라서
\[ x = m_1k_0 + l\frac{m_1m_2}{g} + a_1 \]
또는 $m_1m_2/g$가 $m_1$과 $m_2$의 최소공배수이므로
\[ x \equiv m_1k_0 + a_1 \pmod{\mathrm{lcm}(m_1, m_2)} \]
응용
BOJ 1476:: 날짜 계산
다음 합동식을 만족하는 양의 정수 $x$의 최솟값을 구하면 됩니다.
\begin{align*}
x &\equiv E \pmod{15} \\
x &\equiv S \pmod{28} \\
x &\equiv M \pmod{19} \\
\end{align*}
중국인의 나머지 정리를 쓰면
\[ x \equiv 6916E + 4845S + 4200M \pmod{7980} \]
BOJ 6064:: 카잉 달력
각 테스트 케이스에 대해 다음 합동식을 만족하는 양의 정수 $k$의 최솟값을 구하면 됩니다.
\begin{align*}
k &\equiv x \pmod{M} \\
k &\equiv y \pmod{N}
\end{align*}
위에서 설명한 대로 $y-x$가 $\gcd(M,N)$의 배수여야 합니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
tuple<ll, ll, ll> extended_euclidean(ll a, ll b) {
if (b == 0)
return make_tuple(a, 1, 0);
auto [g, x, y] = extended_euclidean(b, a%b);
return make_tuple(g, y, x-(a/b)*y);
}
int main(void) {
ll t, m, n, x, y, k;
cin >> t;
while (t--) {
cin >> m >> n >> x >> y;
auto [g, k0, _] = extended_euclidean(m, n);
if ((y - x) % g != 0)
cout << "-1" << endl;
else {
k0 *= (y - x) / g;
k = (m * k0 + x) % (m * n / g);
while (k <= 0)
k += m * n / g;
cout << k << endl;
}
}
return 0;
}