中国剰余定理
Abstract
中国剰余定理とその一般化について示す. 一般化中国剰余定理を利用したFraenkelのアルゴリズムについて説明し, Garnerのアルゴリズムがその特殊な場合であることを見る.
Explanation
中国剰余定理
中国剰余定理 (Chinese Remainder Theorem) の主張は, 次のとおりである.
Theorem 1 (中国剰余定理)
与えられた$ k ~ (k \ge 2)個の正整数$ m_1, m_2, \dots, m_kがどの二つも互いに素であるとする.
このとき, 任意に与えられる整数$ a_1, a_2, \dots, a_kに対し, 連立合同式
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ & \vdots \\ x \equiv a_k & \pmod{m_k} \end{cases}
を満たす整数$ xが存在し, この解は$ n_k = m_1 \cdot \cdots \cdot m_kを法として一意的である.
定理の意味
$ xの$ n_kによる剰余を考えることと$ m_1, \dots, m_kによる剰余をまとめて考えることは実質一緒だ, ということを言っている.
特に, ある数$ aの$ nでの剰余を考える場合は, これを直接考える必要はなく,
1. $ nをどの二つも互いに素になるように$ n = m_1 \cdot \dots \cdot m_kと因数分解して, $ n = p_1^{e_1} \cdots p_k^{e_k}となるなら, 例えば$ m_i = p_i^{e_i} ~ (i = 1, \dots, k)とすればよい.
2. 各$ m_iについての剰余を考えてから,
3.$ nでの剰余を再構成することができる,
ということがわかる. 各$ m_iは$ nよりも小さくなるので, $ nがかなり大きい場合の剰余の計算が, それより小さい数での剰余から計算できるのが嬉しい.
Theorem 1の証明では, $ xの各$ m_iについての剰余から$ nでの剰余を具体的に構成する.
Proof
$ kに関する数学的帰納法で示す.
$ k = 2のとき.
◆ 解の構成
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ x \equiv a_2 & \pmod{m_2} \end{cases}
を満たす整数$ xを具体的に構成する.
$ m_1, m_2は互いに素だから, Bézoutの補題 より$ m_1 u + m_2 v = 1を満たす整数解$ (u, v)が存在する. $ (u, v)は 拡張Euclidの互除法 で計算できる. このとき, $ \begin{cases} m_1 u + m_2 v \equiv m_2 v \equiv 1 & \pmod{m_1} \\ m_1 u + m_2 v \equiv m_1 u \equiv 1 & \pmod{m_2} \end{cases}
であるから, $ x = a_2 m_1 u + a_1 m_2 vとすれば
$ \begin{cases} x \equiv a_1 m_2 v \equiv a_1 & \pmod{m_1} \\ x \equiv a_2 m_1 u \equiv a_2 & \pmod{m_2} \end{cases}
となり, 解の構成ができた.
◆ 解の一意性
$ x, yを
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ x \equiv a_2 & \pmod{m_2} \end{cases}
の解とする. このとき,
$ \begin{cases} x - y \equiv 0 & \pmod{m_1} \\ x - y \equiv 0 & \pmod{m_2} \end{cases}
である. $ x - y \equiv 0 \pmod{m_1}より $ x - y = q m_1と書けるから, $ q m_1 \equiv 0 \pmod{m_2}.
ここで, $ m_1, m_2は互いに素であるから, $ qが$ m_2で割り切れなければならず, 整数$ q'を用いて$ q = q' m_2と書ける.
よって
$ x - y = q' m_1 m_2 = q' n_2
となり, $ x - y \equiv 0 \pmod{n_2}, つまり$ x \equiv y \pmod{n_2}である.
$ kまでで主張が成立すると仮定する. $ k+1のときの成立を示す.
帰納法の仮定より
$ \begin{cases} b \equiv a_1 & \pmod{m_1} \\ & \vdots \\ b \equiv a_k & \pmod{m_k} \end{cases}
を満たす整数$ bが$ n_k = m_1 \cdot \cdots \cdot m_kを法として一意的に存在する. $ n_kと$ m_{k+1}は互いに素なので, $ k = 2のときの主張から
$ \begin{cases} x \equiv b & \pmod{n_k} \\ x \equiv a_{k+1} & \pmod{m_{k+1}} \end{cases}
を満たす整数$ xが$ n_{k+1} = n_k \cdot m_{k+1}を法として一意的に存在する. $ \blacksquare
一般化中国剰余定理
実は, Theorem 1の条件, 「与えられた正整数$ m_1, m_2, \dots, m_kがどの二つも互いに素」はもう少し緩めることができる.
Theorem 2 (一般化中国剰余定理)
$ k ~ (k \ge 2)個の正整数$ m_1, m_2, \dots, m_kが与えられたとする.
任意に与えられる整数$ a_1, a_2, \dots, a_kに対し, 連立合同式
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ & \vdots \\ x \equiv a_k & \pmod{m_k} \end{cases}
に解が存在するための必要十分条件は,
$ a_i \equiv a_j \pmod{\gcd(m_i, m_j)} \quad (i, j = 1, \dots, k)
が成立することである. 解が存在するならば, 解$ xは$ \mathop{\mathrm{lcm}}(m_1, \dots, m_k)を法として一意的である.
Proof
以下では, $ g_{i, j} = \gcd(m_i, m_j)とおく.
(必要性)
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ & \vdots \\ x \equiv a_k & \pmod{m_k} \end{cases}
の解を$ yとし, 任意に$ i, j \in \{ 1, \dots, k \}をとる. このとき,
$ \begin{cases} y \equiv a_i & \pmod{m_i} \\ y \equiv a_{j} & \pmod{m_j} \end{cases}
が成り立つ. このとき, 整数$ u, vを用いて$ y = m_i u + a_i = m_j v + a_jと書ける. $ g_{i, j}は$ m_i, m_jの約数なので, 整数$ m_i', m_j'を用いて$ m_i = m_i' g_{i, j}, ~ m_j = m_j' g_{i, j}と書ける. 特に, $ g_{i, j}は最大公約数なので$ m_i', m_j'を互いに素に取れるが, ここでは特にその性質は利用しない. よって,
$ y = m_i' g_{i, j} u + a_i = m_j' g_{i, j} v + a_j
となるので, $ g_{i, j} = \gcd(m_i, m_j)について剰余をとれば
$ a_i \equiv a_j \pmod{\gcd(m_i, m_j)}.
(十分性)
$ kに関する数学的帰納法で示す.
$ k = 2のとき.
◆ 解の構成
$ a_1 \equiv a_2 \pmod{g_{1, 2}}が成立するときに, 解$ xを構成する. まず Bézoutの補題 より$ m_1 u + m_2 v = g_{1, 2}を満たす整数解$ (u, v)が存在する. さて, $ a_1 \equiv a_2 \pmod{g_{1, 2}}であるから, 整数$ qを使って$ a_2 - a_1 = qg_{1, 2}と書ける. よって, $ q m_1 u + q m_2 v = a_2 - a_1 \Longleftrightarrow a_1 + q m_1 u = a_2 - q m_2 v.
よって, $ x = a_1 + m_1 q u = a_2 - m_2 q vとすれば
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ x \equiv a_2 & \pmod{m_2} \end{cases}
となり, 解の構成ができた.
◆ 解の一意性
$ l = \mathop{\mathrm{lcm}}(m_1, m_2)とおく. $ x, yを
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ x \equiv a_2 & \pmod{m_2} \end{cases}
の解とする. このとき,
$ \begin{cases} x - y \equiv 0 & \pmod{m_1} \\ x - y \equiv 0 & \pmod{m_2} \end{cases}
であるから, $ q_1, q_2を整数として, $ x - y = q_1 m_1 = q_2 m_2と書ける. また, $ g_{1, 2}は$ m_1, m_2の最大公約数だから, 互いに素な整数$ m_1', m_2'を用いて$ m_1 = m_1' g_{1, 2}, ~ m_2 = m_2' g_{1, 2}と書ける. これより,
$ q_1 m_1' = q_2 m_2'.
$ m_1', m_2' が互いに素だから, 整数$ q_2'を用いて$ q_2 = q_2' m_1'と書ける. よって,
$ x - y = q_2 m_2 = q_2' m_1' m_2' g_{1, 2} = q_2' l
となり, $ x - y \equiv 0 \pmod{l}, つまり $ x \equiv y \pmod{l}である.
$ kまでで主張が成立すると仮定する. $ k+1のときの成立を示す. 条件
$ a_i \equiv a_j \pmod{g_{i, j}} \quad (i, j = 1, \dots, k+1)
が成立しているので, 帰納法の仮定より
$ \begin{cases} b \equiv a_1 & \pmod{m_1} \\ & \vdots \\ b \equiv a_k & \pmod{m_k} \end{cases}
を満たす整数$ bが$ L_k = \mathop{\mathrm{lcm}} (m_1, \dots, m_k)を法として一意的に存在する. よって, $ x \equiv b \pmod{L_k}が, $ x \equiv a_i \pmod{m_i} \quad (i = 1, \dots, k)であることを保証する.
$ \begin{cases} x \equiv b & \pmod{L_k} \\ x \equiv a_{k+1} & \pmod{m_{k+1}} \end{cases}
の解が一意的に存在することを言えばよい. もし, $ b \equiv a_{k+1} \pmod{\gcd (L_k, m_{k+1})}が成り立てば, 帰納法の仮定から主張が成り立つ. よって, 以下これを示す.
まず$ b \equiv a_i \pmod{m_i}であったから,
$ b \equiv a_i \pmod{g_{i, k+1}}
が成り立つ.$ b \equiv a_i \pmod{m_i}より$ b - a_i = q m_iと表すと, $ m_i = m_i' g_{i, k+1}と表せるので, $ b - a_i = q m_i' g_{i, k+1} \equiv 0 \pmod{g_{i, k+1}}となる.これと条件$ a_i \equiv a_{k+1} \pmod{g_{i, k+1}} \quad (i = 1, \dots, k+1)より,
$ b \equiv a_{k+1} \pmod{g_{i, k+1}} \quad (i = 1, \dots, k+1)
が言えるから
$ b \equiv a_{k+1} \pmod{\mathop{\mathrm{lcm}}\left(g_{1, k+1}, \dots, g_{k, k+1}\right)}
である. ここで, 以下のClaimが成り立つ.
Claim
任意の正整数$ nに対して,
$ \mathop{\mathrm{lcm}}\left(\gcd(m_1, n), \dots, \gcd(m_k, n)\right) = \gcd \left( \mathop{\mathrm{lcm}} \left(m_1, \dots, m_k \right), n\right) \quad (k \ge 2).
Proof
$ kに関する帰納法で示す.
$ k = 2のとき. $ m_1, m_2, nのいずれかを割り切る素数$ p_j ~ (j = 1, \dots, r)を用いて
$ m_1 = \prod_{j=1}^{r} p_j^{e_{j}}
$ m_2 = \prod_{j=1}^{r} p_j^{f_{j}}
$ n = \prod_{j=1}^{r} p_j^{g_{j}}
と素因数分解する (指数$ e_j, f_j, g_jは$ 0以上の整数). 示すべき式は, すべての$ jに対して
$ \max \left( \min \left( e_j, g_j \right), \min \left( f_j, g_j \right) \right) = \min \left( \max \left( e_j, f_j \right), g_j \right)
が成り立つことと同値. $ jを任意に一つ固定する.
$ e_j \le g_j, ~ f_j \le g_jのとき, $ \max (e_j, f_j) \le g_jなので $ (\mathrm{l.h.s.}) = \max (e_j, f_j) = (\mathrm{r.h.s.})となり成立する.
$ e_j > g_jのとき, $ \max (e_j, f_j) \ge e_j > g_jなので, $ (\mathrm{r.h.s.}) = g_j. また, $ \min (e_j, g_j) = g_jで $ \min (f_j, g_j) \le g_jであるから, $ (\mathrm{l.h.s.}) = g_jとなり, 成立.
$ f_j > g_jのときも同様.
$ kまでで正しいと仮定すると,
$ \begin{aligned} & \mathop{\mathrm{lcm}}\left(\gcd(m_1, n), \dots, \gcd(m_k, n), \gcd(m_{k+1}, n)\right) \\ = & \mathop{\mathrm{lcm}}\left( \mathop{\mathrm{lcm}} \left( \gcd(m_1, n), \dots, \gcd(m_k, n)\right), \gcd(m_{k+1}, n)\right) \\ = & \mathop{\mathrm{lcm}}\left( \gcd(L_k, n), \gcd(m_{k+1}, n)\right) \\ = & \gcd \left( \mathop{\mathrm{lcm}} \left(L_k, m_{k+1} \right), n)\right) \\ = & \gcd \left( \mathop{\mathrm{lcm}} \left(L_{k+1} \right), n)\right) \end{aligned}
が成立するので, $ k+1のときも成立する. $ \square
以上のClaimより, $ \mathop{\mathrm{lcm}}\left(g_{1, k+1}, \dots, g_{k, k+1}\right) = \gcd \left( L_k, m_{k+1} \right)であるから,
$ b \equiv a_{k+1} \pmod{\gcd \left(L_k, m_{k+1} \right)}
が成立し, 証明が完了する.$ \blacksquare
上記の十分性の証明は, 連立合同式
$ \begin{cases} x \equiv a_1 & \pmod{m_1} \\ & \vdots \\ x \equiv a_k & \pmod{m_k} \end{cases}
の解の具体的な構成方法を示している.
Algorithm 1 (一般化中国剰余定理を利用した連立合同式の解法)
Input:
長さ$ kの整数列$ (a_1, \dots, a_k)
長さ$ kの非負整数列$ (m_1, \dots, m_k).
Output:1は常に成り立つ式$ x \equiv 0 \pmod{1}を考えていることに対応.
連立合同式$ x \equiv a_i \pmod{m_i} \quad (i = 1, \dots, k) の解が存在するか否か.
存在するならば, 解$ xと$ L_k = \mathop{\mathrm{lcm}}(m_1, \dots, m_k).
2では, 連立合同式$ y \equiv x \pmod{L}, $ y \equiv a_i \pmod{m_i}を考えている.
1. (初期化) $ L \gets 1, $ x \gets 0とする.
2. 各$ i = 1, \dots, kに対して, 以下を行う:
2-1 $ L, m_iの最大公約数$ g = \gcd (L, m_i)と等式$ L u + m_i v = gを満たす整数$ u,vを計算する.2-1は拡張Euclidの互除法 でできる. 2-2 $ a_i - xを$ gで割った商$ qと余り$ rを計算する. もし$ r \neq 0なら, 「解無し」と出力し終了.
2-3 $ x \gets x + Lquと更新した後, $ L \gets \mathop{\mathrm{lcm}} (L, m_i) = L \times \frac{m_i}{g}と更新する. さらにその後, $ x \gets x \bmod Lとする.
3. $ xと$ Lを出力する.2-2では解の存在条件$ x \equiv a_i \pmod{g}が成立することを確認している.
Fraenkelのアルゴリズム
Fraenkelのアルゴリズムは, 上のAlgorithm 1を大きい数の計算が出にくくなるように少しだけ修正したもの. 上のアルゴリズムで大きな数が出るとすれば, 連立合同式
$ \begin{cases} y \equiv x & \pmod{L} \\ y \equiv a_{i} & \pmod{m_{i}} \end{cases}
を解き終わった後の$ xの更新 (手順2-3) の$ Lqu. ここをうまく処理できないか考えてみる. $ g = \gcd (L, m_i)とおく.
第1式$ y \equiv x \pmod{L}より, 整数$ sを用いて$ y = x + Lsと書けるので, 解くべき合同式は
$ Ls \equiv a_i - x \pmod{m_i}
である. 元の連立合同式が解を持つときは, $ x \equiv a_i \pmod{g}が成り立っていた (証明を参照) から, 整数$ qを用いて$ a_i - x = qgと書ける. さらに, $ gが$ L, m_iの最大公約数なので, 互いに素な整数$ L', m_i'を用いて$ L = L' g, ~ m_i = m_i' gと書ける. よって,
$ L' s \equiv q \pmod{m_i'}
となり, 結局これを$ sについて解けば良い.実際, そのような$ sが求まったとすれば, $ L s \equiv a_i - x \pmod{m_i'}が成り立つ. これは, $ L'の$ m_i'に関する モジュラ逆数 (Modular inverse) を$ (L')^{-1}と書けば, $ s \equiv q (L')^{-1} \pmod{m_i'}
で求まる. ここで, 解$ sを$ \bmod ~ m_i'で考えているので, 特に$ s = q (L')^{-1} \bmod m_i'とすることで
$ 0 \le s < m_i'
とすることができる. 以上より, 連立合同式
$ \begin{cases} y \equiv x & \pmod{L} \\ y \equiv a_{i} & \pmod{m_{i}} \end{cases}
の解は, 上の$ sを利用して, $ y = x + L \left( q (L')^{-1} \bmod m_i' \right)と求まる. これが$ \mathop{\mathrm{lcm}}(L, m_i)を法として一意的なのは証明したとおりである.
ところで, $ (L')^{-1}を求めるには,
1. $ L, m_iの最大公約数$ gを計算し,
2.$ L'や$ m_i'を計算し,
とする必要があるように思える. ところが, 実は手順1だけで済む. この手順1は 拡張Euclidの互除法 により計算できるが, この際に $ L u + m_i v = g
を満たす整数$ u, vも計算できる. ここで計算された$ uが$ (L')^{-1}になっている. 実際,
$ L' g u + m_i' g v = g
であるから, 両辺$ gで割って
$ L' u + m_i' v = 1
となり, 両辺$ m_i'で剰余を取ると
$ L' u \equiv 1 \pmod{m_i'}
がわかるので, $ u = (L')^{-1}である.
以上をまとめて, Fraenkelのアルゴリズムを得る.
Algorithm 2 (Fraenkel)
Input:
長さ$ kの整数列$ (a_1, \dots, a_k)
長さ$ kの非負整数列$ (m_1, \dots, m_k).
Output:
連立合同式$ x \equiv a_i \pmod{m_i} \quad (i = 1, \dots, k) の解が存在するか否か.
存在するならば, 解$ xと$ L_k = \mathop{\mathrm{lcm}}(m_1, \dots, m_k).
1. (初期化) $ L \gets 1, $ x \gets 0とする.
2. 各$ i = 1, \dots, kに対して, 以下を行う:
2-1 $ L, m_iの最大公約数$ g = \gcd (L, m_i)と等式$ L u + m_i v = gを満たす整数$ u, vを計算する.
2-2 $ a_i - xを$ gで割った商$ qと余り$ rを計算する. もし$ r \neq 0なら, 「解無し」と出力し終了.
2-3 $ m_i' \gets \frac{m_i}{g}とし, $ s \gets qu \bmod m_i'とする.
2-4 $ x \gets x + Lsと更新した後, $ L \gets \mathop{\mathrm{lcm}} (L, m_i) = L \times m_i'と更新する. さらにその後, $ x \gets x \bmod Lとする.
3. $ xと$ Lを出力する.
結局, Algorithm 1とFraenkelのアルゴリズムの違いは, 解$ xの更新の際に$ xに加えられる項を$ Lqu から$ L (qu \bmod m_i') に変えた点のみ. $ quを$ \bmod ~ m_i'で考えることができるので, 大きな数の演算が出にくくなる.
なお, Garnerのアルゴリズムというものもあるが, これはFraenkelのアルゴリズムで各$ m_i, m_jが互いに素となる特別な場合に利用されるものである.
Implementation
Algorithm 1, Fraenkelのアルゴリズムとも, 入出力は同じ.
Input
整数列 A
非負整数列 M
A と M の要素数は同じ.
Output
解 x
M の要素の最小公倍数 mod
解が存在しない場合は, x, mod = 0, -1 で返すようにしている.
Time complexity
(正確な評価をするには, ビット演算量で評価をする必要がある. Fraenkelのアルゴリズムの方が, 大きい数の演算を避けることができるため, ビット演算量は少ない.)
Algorithm 1の実装
code:python
def extended_euclid(a, b):
x1, y1, m = 1, 0, a
x2, y2, n = 0, 1, b
while m % n != 0:
q, r = divmod(m, n)
x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
return x2, y2, n
def chinese_reminder(A, M):
'''
solve
x \equiv a_1 (mod m_1), ... x \equiv a_k (mod m_k)
by applying the Chinese reminder theorem
Input:
Output:
Returns the tuple (x, mod) of the solution x and the modulus mod = m_1 ... m_k if exists
else (0, -1).
'''
# initialize
x = 0; mod = 1
for a, m in zip(A, M):
u, _, g = extended_euclid(mod, m)
q, r = divmod(a - x, g)
if r != 0: return (0, -1)
x += mod * q * u; mod *= m // g; x %= mod
return x, mod
Algorithm 2 (Fraenkelのアルゴリズム) の実装
code:python
def extended_euclid(a, b):
x1, y1, m = 1, 0, a
x2, y2, n = 0, 1, b
while m % n != 0:
q, r = divmod(m, n)
x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
return x2, y2, n
def fraenkel(A, M):
'''
solve
x \equiv a_1 (mod m_1), ... x \equiv a_k (mod m_k)
by applying the Fraenkel's Algorithm
Input:
Output:
Returns the tuple (x, mod) of the solution x and the modulus mod = m_1 ... m_k if exists
else (0, -1).
'''
# initialize
x = 0; mod = 1
for a, m in zip(A, M):
u, _, g = extended_euclid(mod, m)
q, r = divmod(a - x, g)
if r != 0: return 0, -1
temp = m // g
x += mod * (((q % temp) * (u % temp)) % temp); mod *= temp; x %= mod
return x, mod
Verification
Algorithm 1はPython 3で930 ms. FraenkelのアルゴリズムはPython 3で97 ms.
References
C. Schwarzweller, "The Chinese Remainder Theorem, its Proofs and its Generalizations in Mathematical Repositories". Studies in Logic, Grammar and Rhetoric, 18 (31), 103-119, 2009.
S. Iftene & F. Chelaru, "The general Chinese remainder theorem". International Journal of Computing, 6 (1), 44-50, 2014.
A. S. Fraenkel, "New proof of the generalized Chinese remainder theorem". Proceedings of the American Mathematical Society, 14 (5), 790-791, 1963.