中国剰余定理：合同式の連立解法と応用

定式化と初等的な例

標準的な形では、この定理は x ≡ a1 (mod n1), x ≡ a2 (mod n2), …, x ≡ ak (mod nk) という形の合同式を扱う。法 n1, n2, …, nk が互いに素、すなわち任意の二つの間に 1 より大きい共通の約数がない場合、すべての合同式を同時に満たす整数 x が存在する。また、そのような任意の二つの解は N = n1・n2・…・nk を法として合同である。古典的な例として、兵士を数える逸話がある。例えば、「3人ずつ並べると2人余り、5人ずつでは3人余り、7人ずつでは2人余る」という問題である。法が互いに素であれば、この種の連立方程式には解が存在する。

構成的方法

この定理は解の存在を述べるだけではない。法に関する逆元を用いて解を構成できる。一般的な構成手順は次のとおりである。

1. N = n1・n2・…・nk とし、各 i について Mi = N/ni と置く。
2. Mi の ni を法とする乗法逆元 yi を求める。すなわち、Mi・yi ≡ 1 (mod ni) を満たす yi である。
3. i = 1,…,k にわたる sum(ai・Mi・yi) として x を作り、x を N を法として簡約する。これにより一意な解の合同類が得られる。

この方法は逆元 yi の存在に依存しており、それは法が互いに素であるという仮定から従う。別の手法であるガーナーのアルゴリズムは、大きな中間積を避けながら同じ計算を行い、実際にしばしば用いられる。

一般化と可解条件

法が互いに素でない場合、その連立方程式は解をもつことも、もたないこともある。解が存在するための必要十分条件は、すべての組 i, j について、指定された剰余 ai と aj が gcd(ni,nj) を法として一致することである。解が存在するとき、それらは法の積ではなく、各法の最小公倍数を法として一意である。この一般化された判定基準により、冗長な合同式を系統的に削減し、重なり合う制約を組み合わせることが可能になる。

代数的観点

現代代数学の観点からは、中国剰余定理は環の間の同型を表す。法が互いに素であるとき、Z/NZ は積環 Z/n1Z × Z/n2Z × … × Z/nkZ と同型である。この構造的な記述は、連立合同式を解くことが Z/NZ の元を各成分へ射影することに対応する理由、ならびにそれらの成分から元を復元できる理由を説明する。

応用と意義

この定理には多くの実用的な用途がある。大きな整数に対する高速な算術演算では、より小さな因子を法として計算し、その結果を再結合する手法の基礎となる。この手法は計算機代数や多倍長演算ライブラリで活用されている。また、符号理論、整数復元のアルゴリズム、剰余を別々に保存または処理する分散計算にも現れる。暗号学においても中国剰余定理は標準的な道具である。例えば、暗号システムの実装ではCRTに基づく最適化がしばしば利用され、RSAなどの公開鍵方式のアルゴリズム的文脈では、復号や署名の処理を高速化するためにCRTが役立つ。

合同と整除性の基礎については、合同算術および合同式に関する一般的な文献を参照されたい。互いに素という条件と関連する数論的概念については、互いに素な整数に関する資料が参考になる。さらに技術的・歴史的な資料は、数論の標準的な教科書や概説論文で参照できる。