1. 概要

本記事では，中国剰余定理（Chinese Remainder Theorem, CRT）について解説します．中国剰余定理は，どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ に対して，合同式

$$ x\equiv a _ 0\pmod{m _ 0},\quad x\equiv a _ 1\pmod{m _ 1},\quad \cdots,\quad x\equiv a _ {n-1}\pmod{m _ {n-1}} $$

を同時に満たす整数 $x$ の存在（および $m_0m_1\cdots m_{n-1}$ を法とする一意性）を保証する定理です．定理の証明や，そのような $x$ を求めるアルゴリズムを理解することが本講座のひとつの目標です．

さらに中国剰余定理を用いると，合成数を法とする合同式に関する問題を，素数のべき乗を法とする合同式に関する問題へと分解して扱うことができます．本記事ではそのような応用も重視しながら，中国剰余定理について解説します．

2. 前提知識

AtCoder Algorithm Lectures における次の講座の内容を前提とします．

3. 中国剰余定理

3.1. 定理の主張

【定理 1】（中国剰余定理）

$m_0,m_1,\ldots,m_{n-1}$ を正整数とし，どの $2$ つも互いに素であるとする．$a_0,a_1,\ldots,a_{n-1}$ を整数とする．このとき

$$ x\equiv a_i\pmod{m_i}\quad (0\leq i < n) $$

を満たす整数 $x$ が存在する．さらにこのような $x$ は $M=m_0m_1\cdots m_{n-1}$ を法として一意である．

3.2. 具体例

例えば $m_0=3, m_1=5$ とします．$M=m_0m_1=15$ とすれば，$x\bmod M$ の値から $x\bmod m_0, x \bmod m_1$ の値が定まります．その対応は以下の表のようになります．

$x=0,1,\ldots,14$ に対して組 $(x\bmod 3, x\bmod 5)$ を考えると，

$$ (a_0,a_1)\quad (0\leq a_0 < 3,0\leq a_1 < 5) $$

となる組がすべてちょうど $1$ 度ずつ現れており，定理が成り立つことが確かめられます．

3.3. 定理の証明

写像

$$ f\colon [0,M) \longrightarrow [0,m_0) \times [0,m_1)\times \cdots \times [0,m_{n-1}) $$

を，

$$ f(x) = \left(x \bmod m_0, x\bmod m_1,\ldots, x\bmod m_{n-1}\right) $$

により定めます．まず $f$ が単射である，つまり $f(x)=f(y)$ ならば $x=y$ が成り立つことを示します．

$f(x)=f(y)$ であるとすると，各 $i$ に対して $(x\bmod m_i)=(y\bmod m_i)$ より $x-y$ は $m_i$ の倍数です．したがって $x-y$ は $m_0,m_1,\ldots,m_{n-1}$ の公倍数です．

$m_0,m_1,\ldots,m_{n-1}$ がどの $2$ つも互いに素であることから，これらの最小公倍数はその総積 $M$ と一致します．したがって $x-y$ は $M$ の倍数となりますが，$x,y\in [0,M)$ よりこれが成り立つのは $x=y$ である場合に限られます．以上で $f$ が単射であることがいえました．

一般に写像 $f\colon A\longrightarrow B$ について，$|A|=|B|$ かつ $f$ が単射ならば $f$ は全単射なので，上の $f$ も全単射です．したがって任意の

$$(a_0, a_1, \ldots, a _ {n-1}) \in [0,m_0) \times [0,m_1)\times \cdots \times [0, m _ {n-1})$$

に対して $f(x)=(a_0,a_1,\ldots,a_{n-1})$ を満たす $x\in [0,M)$ がちょうど $1$ つ存在します．これが示すべきことでした．$\blacksquare$

4. アルゴリズム

中国剰余定理をもとに，次の問題を考えます．

【問題 2】

どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ および，整数 $a_0,a_1,\ldots,a_{n-1}$ が与えられます．

$$ x\equiv a_i\pmod{m_i}\quad (0\leq i\leq n-1) $$

を満たす最小の非負整数 $x$ を出力してください．

【定理 1】から，

$$x\equiv a_i\pmod{m_i}\quad (0\leq i\leq n-1)$$

には解が存在し，しかもその解は $M=\prod_{i=0}^{n-1} m_i$ を法として一意です．したがって，$x=0,1,\ldots,M-1$ の $M$ 通りを全探索することでも解は得られますが，ここではより高速に解を求める方法を考えます．特に代表的な $2$ つの解法を扱います．

4.1. 方法 1

$M=\prod_{i=0}^{n-1} m_i$ とし，各 $i$ について

$$ M_i=\frac{M}{m_i}=\prod_{j\ne i}m_j $$

とします．$m_i$ と $M_i$ は互いに素なので，$M_i$ の $m_i$ を法とする乗法逆元が存在します．そのひとつを $x_i$ とし，$e_i=x_iM_i$ とします．このとき，

$$ e_i\equiv 1\pmod{m_i},\qquad e_i\equiv 0\pmod{m_j} \quad (j\neq i) $$

が成り立ちます．したがって，

$$ x=\sum_{i=0}^{n-1} a_ie_i $$

が【問題 2】の条件を満たすことが分かります．

疑似コードにすると次のようになります．

function CRT(a, m, n):
  M := 1
  for i = 0, 1, ..., n - 1:
    M *= m[i]

  x = 0
  for i = 0, 1, ..., n - 1:
    Mi := M / m[i]
    xi := inverse of Mi modulo m[i]
    ei := Mi * xi mod M
    x = (x + a[i] * ei) mod M
    
  return x

$M = \prod_{0\leq i < n} m_i$ 以下の非負整数に関する四則演算の計算が $\mathrm{O}(1)$ 時間で行える場合，【問題 2】を $\mathrm{O}(n + \log M)$ 時間で解くことができます．

【問題 3】

$x\equiv 1\pmod{100}$, $x\equiv 0\pmod{101}$ を満たす整数 $x$ をひとつ求めてください．
$x\equiv 0\pmod{100}$, $x\equiv 1\pmod{101}$ を満たす整数 $x$ をひとつ求めてください．
$x\equiv 23\pmod{100}$, $x\equiv 45\pmod{101}$ を満たす整数 $x$ をひとつ求めてください．

解説

1 は $x=101$，2 は $x=-100$ が条件を満たします．したがって $e_0=101, e_1=-100$ とすると，$x=a_0e_0+a_1e_1$ が

$$ x\equiv a_0\pmod{100},\quad x\equiv a_1\pmod{101} $$

を満たします．これが「方法 1」のアイデアです．$x=23\cdot 101-45\cdot 100=-2177$ が 3 の解のひとつです．なお，非負整数かつ最小の解は $-2177+100\cdot 101=7923$ です．

4.2. 方法 2

$x_0=0$ とする．
$i=0$ に関する条件を満たす最小の非負整数を $x_1$ とする．
$i=0,1$ に関する条件を満たす最小の非負整数を $x_2$ とする．
$\vdots$

として，$x_1,x_2,\ldots,x_n$ を順に求めていくことを考えます．

$x_k$ まで求まったとして，$x _ {k+1}$ を求めることを考えましょう．$x_k$ は最初の $k$ 個の条件を満たす最小の非負整数でした．$x _ {k+1}$ も最初の $k$ 個の条件を満たすことから，ある非負整数 $c_k$ に対して

$$ x _ {k+1}=x_k + c_k m_0 m_1 \cdots m _ {k-1} $$

と表すことができます．これが $x_{k+1}\equiv a_k\pmod{m_k}$ を満たすような非負整数 $c_k$ を求めればよいです．

これは $c_k$ に関する $1$ 次合同式と見なすことができます．$m_k$ と $m_0 m_1 \cdots m _ {k-1}$ は互いに素なので，$m_0 m_1 \cdots m _ {k-1}$ は $m_k$ を法として乗法逆元を持ちます．したがって，この合同式は $m_k$ を法として一意な解を持ち，その解は $m_k$ を法とする $m_0m_1\cdots m_{k-1}$ の乗法逆元を用いて求めることができます（Euclid の互除法参照）．

疑似コードにすると次のようになります．

function CRT(a, m, n):
  m_prod = 1
  x = 0
  for i = 0, 1, ..., n - 1:
    // solve x + c * m_prod ≡ a[i] (mod m[i])
    y := inverse of m_prod modulo m[i]
    c := y * (a[i] - x) mod m[i]
    x += c * m_prod
    m_prod *= m[i]

  return x

$x$ の混合基数表現について

上の方法で求めた $c_0,c_1,\ldots,c_{n-1}$ と最終的な解 $x$ は，次を満たします：

$$ x = c_0 + c_1 m_0 + c_2m_0m_1 + \cdots + c _ {n-1}m_0m_1\cdots m _ {n-2},\quad 0\leq c_i < m_i (0\leq i < n) $$

このように $x$ を表すことを，$x$ の混合基数表現（mixed radix representation）といいます．

【問題 4】

$x\equiv 1\pmod{2}$, $x\equiv 3\pmod{5}$ を満たす最小の非負整数 $x$ を求めてください．
$x\equiv 1\pmod{2}$, $x\equiv 3\pmod{5}$, $x\equiv 10\pmod{11}$ を満たす最小の非負整数 $x$ を求めてください．
$x\equiv 1\pmod{2}$, $x\equiv 3\pmod{5}$, $x\equiv 10\pmod{11}$, $x\equiv 4\pmod{7}$ を満たす最小の非負整数 $x$ を求めてください．
3 で求めた $x$ を $$ x=c_0+2c_1+10c_2+110c_3 $$ （ただし $0\leq c_0 < 2, 0\leq c_1 < 5, 0\leq c_2 < 11, 0\leq c_3 < 7$）の形に表してください．

解説

$x=1+2c_1$ が $x\equiv 3\pmod{5}$ を満たすように $c_1$ を定めると，$c_1=1, x=3$ が得られます．
$x=3+10c_2$ が $x\equiv 10\pmod{11}$ を満たすように $c_2$ を定めると，$c_2=4, x=43$ が得られます．
$x=43+110c_3$ が $x\equiv 4\pmod{7}$ を満たすように $c_3$ を定めると，$c_3=2, x=263$ が得られます．
上の議論から，$c_0=1,c_1=1,c_2=4,c_3=2$ が条件を満たします．

4.3. 総積 $M$ が大きい場合の計算について

方法 1，方法 2 では，総積 $M$ 以下の非負整数に対する四則演算の計算量が $\mathrm{O}(1)$ 時間であると仮定した場合に，【問題 2】が $\mathrm{O}(n+\log M)$ 時間で解けることを確認しました．ここでは総積 $M$ が巨大で，このような仮定をおけない場合の方法について考えます．

このような状況では，これまで紹介した実装をそのまま使おうとすると桁数が巨大な多倍長整数の演算を行う必要が出てきてしまいます．そもそも問題の出力が一般には巨大になるため，これは避けられません．一方で，競技プログラミングでは次の形式の問題を扱うこともあります．

【問題 5】

どの $2$ つも互いに素であるような正整数 $m_0,m_1,\ldots,m_{n-1}$ および，整数 $a_0,a_1,\ldots,a_{n-1}$ が与えられます．さらに，正整数 $m'$ が与えられます．

$$ x\equiv a_i\pmod{m_i}\quad (0\leq i\leq n-1) $$

を満たす最小の非負整数 $x$ を，$\bmod m'$ で出力してください．

制約：$m_i\leq 10^9,\quad m'\leq 10^9$．

この場合には，問題の出力は $m'$ 未満なので，多倍長整数を用いない解法があるかもしれません．

方法 2 を上手く利用することで，そのような解法が可能です．方法 2 は，最初の $k$ 個の条件を満たす最小の非負整数 $x_k$ について，その混合基数表現

$$ x_k = c_0 + c_1m_0 + c_2m_0m_1 + \cdots + c _ {k - 1} m_0m_1\cdots m _ {k-2},\quad 0\leq c_i < m_i (0\leq i < k) $$

を求めるものでした．4.2 節で解説した疑似コードでは，$c_0,c_1,\ldots$ を求めると同時に $x_0,x_1,\ldots$ も求めていますが，このアルゴリズムを $c_i$ のみを求めて保持する形に変えてみましょう．すると，次のような疑似コードのアルゴリズムが得られます．

function CRT(a, m, n):
  c := array of length n
  for i = 0, 1, ..., n - 1:
    // Here, xi = c[0] + c[1]m[0] + ... + c[i-1]m[0]m[1]...m[i-2]
    // is the solution to first i conditions. 

    // calculate xi modulo m[i]. 
    xi := 0
    m_prod := 1
    for j = 0, 1, ..., i - 1:
      xi = (xi + c[j] * m_prod) mod m[i]
      m_prod = (m_prod * m[j]) mod m[i]
    
    // solve xi + c[i] * m_prod ≡ a[i] (mod m[i])
    y := inverse of m_prod modulo m[i]
    c[i] = y * (a[i] - xi) mod m[i]

  return c

このアルゴリズムによって，最小解 $x$ の混合基数表現

$$ x = c_0 + c_1 m_0 + c_2m_0m_1 + \cdots + c _ {n-1}m_0m_1\cdots m _ {n-2},\quad 0\leq c_i < m_i (0\leq i < n) $$

の係数 $c_0, c_1, \ldots, c _ {n-1}$ が $\mathrm{O}(n ^ 2 + n \log \max(m _ 0, m _ 1, \ldots, m _ {n-1}))$ 時間で計算できます．これを用いると，【問題 5】は $\mathrm{O}(n ^ 2+n \log \max(m_0,m_1,\ldots,m_{n-1}))$ 時間で解くことができます．

最小解 $x$ を多倍長整数として出力する場合

$x$ の混合基数表現

$$ x=c_0+c_1m_0+c_2m_0m_1+\cdots + c _ {n-1}m_0m_1\cdots m _ {n-2} $$

を用いると，$x$ を次のようなアルゴリズムによって計算することができます．

function calc_x(c, m, n):
  x := 0
  for i = n - 1, n - 2, ..., 0:
    x = x * m[i] + c[i]
  return x

$N$ 桁の整数を長さ $N$ の配列によって表すような標準的な多倍長整数の実装を用いれば，$\mathrm{O}(n ^ 2+n \log \max(m_0,m_1,\ldots,m_{n-1}))$ 時間で $x$ を多倍長整数として求めることができます．

なお，分割統治法や FFT，half-gcd といった高度なアルゴリズムを利用すれば，【問題 2】の解を多倍長整数として出力するよりも計算量オーダーの良い解法が得られますが，本記事では解説を省略します．

Garner のアルゴリズムについて

最小解 $x$ の混合基数表現について，以下のようなアルゴリズムを解説しました．

総積 $M$ が小さい場合に，$\mathrm{O}(n+\log M)$ 時間で $x$ の混合基数表現を求める．
総積 $M$ が大きい場合に，$\mathrm{O}(n ^ 2+n \log \max(m_0,m_1,\ldots,m_{n-1}))$ 時間で $x$ の混合基数表現を求める．
$x$ の混合基数表現を求め，それを利用して $x$ を多倍長整数として求める．
$x$ の混合基数表現を求め，それを利用して $x\bmod m'$ を求める．

これらのアルゴリズムはいずれも，混合基数表現を順に求めるという Garner による考え方（文献 4）に基づいており，Garner のアルゴリズムと呼ばれることがあります．ただし，この呼称が指す内容には文献による揺れがあるようです．

5. 中国剰余定理の応用

5.1. Euler の totient 関数

Euler の totient 関数は，原始根でも扱いました．改めて定義を確認します．

【定義 6】（Euler の totient 関数）

正整数 $n$ に対して，$0$ 以上 $n-1$ 以下の整数のうち $n$ と互いに素なものの個数を $\varphi(n)$ と書く．$\varphi$ を Euler の totient 関数（Euler's totient function）という．

小さな $n$ に対する $\varphi(n)$ の値は次の表の通りです．

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\varphi(n)$	$1$	$1$	$2$	$2$	$4$	$2$	$6$	$4$	$6$	$4$

【定理 7】

正整数 $n$ の素因数分解を $n=\prod_{i=0}^{k-1}p_i^{e_i}$ （ただし $e_i>0$）とするとき，次が成り立つ：

$$\varphi(n)=n\prod_{i=0}^{k-1}\left(1-\frac{1}{p_i}\right)$$

$x$ が $n$ と互いに素であることは，各 $i$ について

$$ x\equiv 1, 2, \ldots, p_i - 1\pmod{p_i} $$

のいずれかが成り立つことと同値です．中国剰余定理より，このような $x$ は $\prod_i p_i$ を法として $\prod _ {i = 0} ^ {k - 1} (p_i-1)$ 個存在します．$0$ 以上 $n-1$ 以下の範囲には，その $n / \prod_{i=0}^{k-1}p_i$ 倍である

$$n\prod_{i=0}^{k-1}\left(1-\frac{1}{p_i}\right)$$

個存在します． $\blacksquare$

例えば次が成り立ちます．

$\displaystyle \varphi(1000)=1000\cdot \frac12\cdot \frac45=400$．
$\displaystyle \varphi(2310)=2310\cdot \frac12 \cdot \frac23 \cdot \frac45 \cdot \frac 67\cdot \frac{10}{11}=480$．

5.2. 合成数を法とする合同式

中国剰余定理は，合成数を法とする合同式を扱うときにも重要です．特に，合成数を法とする問題を，素数のべき乗を法とする問題に分割して考えるという使い方が標準的です．

ここでは，そのような考え方をいくつかの問題を通して紹介します．なお本節で扱う問題はプログラムを書かずに簡単な手計算で解けることが想定されています．

【問題 8】
次の値を求めてください．

$2 ^ {2026}\bmod 105$．
$2 ^ {2026}\bmod 720$．

解説

$105 = 3\cdot 5\cdot 7$ であるから，答を $\bmod 3, \bmod 5, \bmod 7$ で求めることができれば，そこから答を求めることができます．$2 ^ n$ は $3, 5, 7$ を法としてそれぞれ簡単な周期数列で，$x = 2 ^ {2026}$ とすれば $x\equiv 1\pmod{3}$，$x\equiv 4\pmod{5}$，$x\equiv 2\pmod{7}$ となることが簡単に分かります．ここから $x\equiv 79\pmod{105}$ が得られます．
$720 = 16\cdot 9\cdot 5$ であるから，答を $\bmod 16, \bmod 9, \bmod 5$ で求めることができれば，そこから答を求めることができます．（$16=2 ^ 4$ ですが，$\bmod 2$ での値を $4$ 回求めるというような方法をとることはできないことに注意してください）．$x=2 ^ {2026}$ とすれば $x\equiv 0\pmod{16}$，$x\equiv 7\pmod{9}$，$x\equiv 4\pmod{5}$ となり，ここから $x\equiv 304\pmod{720}$ が得られます．

【問題 9】
$x ^ 2\equiv x\pmod{100}$ を満たす整数 $x$ ($0\leq x < 100$) をすべて求めてください．

解説

$x ^ 2\equiv x\pmod{100}$ であることは $x ^ 2\equiv x\pmod{4}$ かつ $x ^ 2\equiv x\pmod{25}$ と同値です．例えば $x=0,1,2,3$ の $4$ 通りを試せば，

$$x ^ 2\equiv x\pmod{4}\iff x\equiv 0,1\pmod{4}$$

であることが分かります（あるいは次の $\pmod{25}$ の場合と同様の議論をしてもよいです）．

$x ^ 2\equiv x\pmod{25}$ は，$x(x-1)$ が $25$ の倍数であることと同値ですが，$x, x-1$ が同時に $5$ の倍数となることはないのでこれは $x, x-1$ のどちらかが $25$ の倍数であることと同値です．したがって

$$x ^ 2\equiv x\pmod{25}\iff x\equiv 0,1\pmod{25}$$

であることが分かります．よって $x ^ 2\equiv x\pmod{100}$ であることは，次のいずれかが成り立つことと同値です．

$x\equiv 0\pmod{4},\quad x\equiv 0\pmod{25}$
$x\equiv 0\pmod{4},\quad x\equiv 1\pmod{25}$
$x\equiv 1\pmod{4},\quad x\equiv 0\pmod{25}$
$x\equiv 1\pmod{4},\quad x\equiv 1\pmod{25}$

それぞれに対して $x$ が $100$ を法として唯一存在するということが中国剰余定理により分かります．具体的に求めると，$x \equiv 0,76,25,1\pmod{100}$ となり，$100$ 未満の非負整数としては $x=0,76,25,1$ の $4$ つが求めるものです．

【問題 10】
次の個数を求めてください（計算式を答えてください）．

$n=840$ とするとき，$x^2\equiv 1\pmod{n}$ を満たす整数 $x$（$0\leq x < n$）の個数．
$n=11\times 13\times 17\times 19$ とするとき，$x^3\equiv 1\pmod{n}$ を満たす整数 $x$（$0\leq x < n$）の個数．
$n=11\times 13\times 17\times 19$ とするとき，$n$ を法とする $3$ 乗数，つまりある整数 $y$ に対して $x\equiv y ^ 3\pmod{n}$ が成り立つような $x$（$0\leq x < n$）の個数．

解説

原始根を用いた議論を行っている部分については，原始根の特に 6.2 節を参照してください．

$x ^ 2\equiv 1\pmod{840}$ であることは $x ^ 2\equiv 1\pmod{8}$，$x ^ 2 \equiv 1\pmod{3}$，$x ^ 2 \equiv 1\pmod{5}$，$x ^ 2 \equiv 1\pmod{7}$ がすべて成り立つことと同値です．$x^2\equiv 1\pmod{8}$ は $x\equiv 1, 3, 5, 7 \pmod{8}$ と同値であり，$p = 3, 5, 7$ に対して $x^2\equiv 1\pmod{p}$ は $x\equiv \pm 1\pmod{p}$ と同値です．これらの解の個数を掛け合わせた $4\cdot 2\cdot 2\cdot 2=32$ が求める個数となります．なお因数分解 $x ^ 2 - 1 = (x + 1) (x - 1)$ を使う議論や，原始根を使う議論によって，奇素数 $p$ に対して $x ^ 2\equiv 1\pmod{p}\iff x\equiv \pm 1\pmod{p}$ を示すことができます．
これまでと同様に，$p=11,13,17,19$ それぞれについて $x ^ 3\equiv 1\pmod{p}$ を満たす $x$（$0\leq x < p$）の個数を求め，かけ合わせればよいです．それぞれ原始根を $g$ とすれば，
- $p=11$：$x\equiv g ^0\pmod{p}$ の $1$ 個
- $p=13$：$x\equiv g ^ 0, g ^ 4, g ^ 8\pmod{p}$ の $3$ 個
- $p=17$：$x\equiv g ^ 0\pmod{p}$ の $1$ 個
- $p=19$：$x\equiv g ^ 0\pmod{p}, g ^ 6, g ^ {12}$ の $3$ 個
の解がある．答は $1\times 3\times 1\times 3=9$ 個である．
やはり $p=11,13,17,19$ それぞれについて，$p$ を法とする $3$ 乗数の個数を求め，かけ合わせればよいです．それぞれ原始根を $g$ とすれば，
- $p=11$：$x\equiv 0, g ^ 0, g ^ 1, \ldots, g ^ {9}$ の $11$ 個
- $p=13$：$x\equiv 0, g ^ 0, g ^ 3, g ^ 6, g ^ 9\pmod{p}$ の $5$ 個
- $p=17$：$x\equiv 0, g ^ 0, g ^ 1, \ldots, g ^ {15}$ の $17$ 個
- $p=19$：$x\equiv 0, g ^ 0, g ^ 3, g ^ 6, g ^ 9, g ^ {12}, g ^ {15}$ の $7$ 個
の解がある．答は $11\times 5\times 17\times 7$ 個である．

【問題 11】
$n=11\times 13\times 17\times 19$ とするとき，整数 $x$ について $\gcd(x,n)=1\implies x ^ k\equiv 1 \pmod{n}$ が成り立つような正整数 $k$ のうちで最小のものを求めてください．

解説

正整数 $k$ が問題の条件を満たすことは，$p=11, 13, 17, 19$ に対して次が成り立つことと同値です：$x=1,2,\ldots,p-1$ に対して $x ^ k \equiv 1 \pmod{p}$．原始根の存在定理から，これは $k$ が $p - 1$ の倍数であることと同値です．

本問の答は，$10,12,16,18$ の最小公倍数である $720$ となります．

5.3. 巨大な整数の復元

$M=m_0m_1\cdots m_{n-1}$ とし，非負整数 $x$ が $0\leq x < M$ を満たすとします．このとき，各 $i$ について $x\bmod m_i$ を求めることができれば，中国剰余定理によって $x$ を一意に求めることができます．

例えば非負整数 $x$ について $0\leq x < 10^{18}$ であることが分かっているとき，

$x \pmod{10 ^ 9+7}$
$x \pmod{10 ^ 9+9}$

が求まれば $x$ を求めることができます．（$10 ^ 9+7, 10 ^ 9+9$ は素数です．）

多項式乗算（畳み込み）や，数え上げに関する問題では，$x$ そのものを計算することよりも，いくつかの素数を法として $x$ を求めることの方が簡単に行えることがあり，このような手順が有効になります．

AtCoder ユーザーに有名な例としては，AtCoder Library による convolution_ll の実装が挙げられます．

AtCoder Library．https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp．

詳細な解説は本記事のレベルを超えるため省略しますが，ここでの計算は特定の素数を法として $64$ ビットに収まる整数の計算をする際に，$3$ つの素数を法とした値を計算し，そこから $x$ を中国剰余定理で復元しています．

6. 関連問題

問題について

1 は $n=2$ の場合の中国剰余定理のような設定で解 $x$ を求める問題です．制約が小さいため全探索のような解法でも正解できますが，本記事で解説したアルゴリズムも試してみてください．

2, 3 も中国剰余定理のような設定ですが，法 $m_i$ に互いに素という条件が課せられていないというところについて工夫が必要です．また 4 ではさらに条件の追加削除も要求されており，さらに難易度は高いです．

5, 6, 7, 8 はいくつかの法に関する条件を同時に満たす整数を調べる問題に帰着できる問題です．9 はいくつかの法に関する値から巨大な整数を復元することに関する問題です．

10, 11 は中国剰余定理によって方程式の解を調べることで解ける問題です．

12 は中国剰余定理を題材とした難易度の高い問題です．

7. まとめ

本記事では，中国剰余定理を証明し，さらに具体的に解 $x$ を求めるアルゴリズムについても解説しました．

解を求める方法としては，4.1 節の「方法 1」と 4.2 節の「方法 2」を紹介しました．4.1 節の「方法 1」は，各 $a_i$ が解にどのように寄与するか理解しやすい方法です．一方で，4.2 節の「方法 2」は最小の非負整数解を表しやすい方法で，特にその混合基数表現を求めることができます．

なお中国剰余定理は，多項式を法とする合同式（あるいはより一般に環のイデアルに関する合同式）にも一般化することができて，多項式補間の問題とも密接な関係があります．「方法 1」「方法 2」はそれぞれ，多項式補間では Lagrange 補間，Newton 補間と呼ばれる方法に対応します．

中国剰余定理についてはこれらのアルゴリズムによって解を求められるようになるだけでなく，合成数を法とする合同式の問題を，素数や素数のべき乗の場合に分解して調べるという応用も重要です．特に 5.2 節の問題を通して，そのような考え方を確認していただければと思います．

また，中国剰余定理には，二項係数を合成数を法として計算したり，畳み込みの計算においていくつかの法での値から巨大な答えを復元するといった応用もあり，AtCoder Algorithm Lectures 内でもこのような考え方が使われる機会があると思います．

8. 参考文献

Wikipedia．中国の剰余定理．https://ja.wikipedia.org/wiki/中国の剰余定理．（閲覧日: 2026-04-04）．
cp-algorithms．Chinese Remainder Theorem．https://cp-algorithms.com/algebra/chinese-remainder-theorem.html．（閲覧日: 2026-04-04）．
USACO Guide．Extended Euclidean Algorithm．https://usaco.guide/adv/extend-euclid．（閲覧日: 2026-04-04）．
Harvey L. Garner．The Residue Number System．IRE Transactions on Electronic Computers．Vol. EC-8．No. 2．pp. 140–147．1959．DOI: 10.1109/TEC.1959.5219515．https://doi.org/10.1109/TEC.1959.5219515．
kirika_comp．Garner のアルゴリズムと多倍長整数演算．https://kirika-comp.hatenablog.com/entry/2017/12/18/143923．（閲覧日: 2026-04-04）．
anta．中華風剰余定理．yukicoder wiki．https://yukicoder.me/wiki/中華風剰余定理．（閲覧日: 2026-04-04）．
けんちょん．中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ．https://qiita.com/drken/items/ae02240cd1f8edfc86fd．（閲覧日: 2026-04-04）．

トップページ：AtCoder Algorithm Lectures