中国剰余定理

数学において、中国剰余定理とは、整数nを複数の整数でユークリッド除算した際の剰余がわかっている場合、約数が互いに素であるという条件（どの 2 つの約数も 1 以外の共通因数を持たない）の下で、これらの整数の積でn を除算した際の剰余を一意に決定できることを述べています。

この定理は孫子の定理と呼ばれることもあります。定理のどちらの名前も、紀元3世紀から5世紀にかけて書かれた中国の写本『孫子算経』に登場する最も古い記述に由来しています。この最初の記述は、次の例に限定されていました。

n を3 で割った余りが 2、 nを 5 で割った余りが3、nを7 で割った余りが 2 であることがわかっていれば、他の情報がなくても、nを105 (3、5、7 の積) で割った余りが 23 であると判断できます。さらに、23 は 105 未満の唯一の正のnの値です。

中国剰余定理は、結果のサイズの上限がわかっている計算を、小さな整数での複数の同様の計算に置き換えることができるため、大きな整数での計算に広く使用されています。

中国剰余定理（合同式で表現）は、あらゆる主イデアル領域で成り立ちます。この定理は、両側イデアルを含む定式化により、任意の環に一般化されています。

この問題に関する最も古い記述は、5世紀の中国の数学者孫子の著書『孫子算経』^{に記載されている。 [1]}

数が分からないものがあります。3ずつ数えると2つ余ります。5ずつ数えると3つ余ります。7ずつ数えると2つ余ります。何個あるでしょうか？^[2]

孫子の著作は、現代の基準では定理とはみなされないだろう。孫子は特定の問題を1つ提示しているだけで、その問題を解く方法を示しておらず、一般的なケースの証明や一般的な解法は言うまでもない。^[3]この問題を解くアルゴリズムに相当するものは、アーリヤバータ（6世紀）によって記述されている。^[4]中国の剰余定理の特殊なケースは、ブラフマグプタ（7世紀）にも知られており、フィボナッチの算盤書（1202年）にも登場する。^{[5]この結果は後に、}秦九紹の1247年の九部数学論で「大衍術」と呼ばれる完全な解法で一般化され、^{[6]は19世紀初頭にイギリスの宣教師}アレクサンダー・ワイリーによって英訳された。^[7]

合同の概念は、カール・フリードリヒ・ガウスが1801年に著した『算術論』で初めて導入され、使用された。^[9]ガウスは、暦に関する問題、すなわち「太陽と月の周期とローマ暦に関して特定の周期数を持つ年を見つける」という問題で中国の剰余定理を例証している。^{[10]ガウスは、}レオンハルト・オイラーがすでに使用していた問題を解く手順を導入したが、実際には何度も登場していた古代の方法であった。^[11]

n ₁ , ..., n _kを 1 より大きい整数とします。これらはしばしば法または約数と呼ばれます。n _iの積をNで表します。

中国剰余定理は、n _iが互いに素であり、a ₁、...、a _{k が}任意のiに対して0 ≤ a _i < n _iとなる整数である場合、 0 ≤ x < Nとなる整数xが 1 つだけ存在し、 xをn _iでユークリッド除算した剰余は任意の i に対してa i_となることを主張します。

これを合同性の観点から次のように言い換えることができる。もしが互いに素であり、a ₁ , ..., a _{k が}任意の整数であれば、 ${\displaystyle n_{i}}$

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

解が存在し、任意の２つの解、例えばx ₁とx _2はN を法として合同である、つまりx ₁ ≡ x ₂ (mod N  )である。^[12]

抽象代数学では、この定理は次のように言い換えられることが多い。n i_が互いに素である場合、写像

${\displaystyle x{\bmod {N}}\;\mapsto \;(x{\bmod {n}}_{1},\,\ldots ,\,x{\bmod {n}}_{k})}$

環同型を定義する^[13]

${\displaystyle \mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }$

N を法とする整数の環とn _{i を}法とする整数の環の直積との間の関係です。つまり、 で一連の算術演算を実行する場合、それぞれで独立に同じ計算を実行し、次に同型性を適用して (右から左へ) 結果を得ることができます。 Nと演算数が大きい場合、これは直接計算よりもはるかに高速です。 これは、マルチモジュラ計算という名前で、整数または有理数上の線型代数に広く使用されています。 ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$

この定理は、組合せ論の言語で、整数の無限等差数列がヘリー族を形成するという事実として言い換えることもできる。^[14]

解の存在と一意性は独立して証明できます。ただし、以下に示す最初の存在証明では、この一意性を利用しています。

xとy が両方ともすべての合同式の解であると仮定します。 xとy をn _iで割ったときの剰余は同じなので、それらの差x − yは各n _iの倍数になります。n _{i は}互いに素なので、それらの積Nもx − y を割り切るので、xとy はN を法として合同です。xとy が 非負でN未満であると仮定すると(定理の最初のステートメントのように)、それらの差がNの倍数になるのはx = yの場合のみです。

地図

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})}$

は、 Nを法とする合同類を、 n _iを法とする合同類の列に写像します。一意性の証明は、この写像が単射であることを示しています。この写像の定義域と余域には同じ数の要素があるため、写像は全射でもあり、解の存在が証明されます。

この証明は非常に単純ですが、解を計算する直接的な方法は提供していません。さらに、次の証明が可能な他の状況に一般化することはできません。

存在はxの明示的な構成によって確立される。^{[15]この構成は2つのステップに分けることができ、まず2つのモジュライの場合の問題を解き、次にモジュライの数に関する}帰納法によってこの解を一般の場合に拡張する。

私たちは次のシステムを解決したいと考えています:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}}$

ここで、 とは互いに素です。 ${\displaystyle n_{1}}$${\displaystyle n_{2}}$

ベズーの恒等式は、 2 つの整数とが存在し、${\displaystyle m_{1}}$${\displaystyle m_{2}}$

${\displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}$

整数およびは、拡張ユークリッドの互除法によって計算できます。 ${\displaystyle m_{1}}$${\displaystyle m_{2}}$

解は次のようになる。

${\displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}$

確かに、

${\displaystyle {\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}}$

2 番目の合同は、下付き文字 1 と 2 を交換することによって同様に証明されます。 ${\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.}$

合同方程式のシーケンスを考えてみましょう。

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}$

ここで、は互いに素である。最初の2つの方程式は、前のセクションの方法で解が与えられている。これらの最初の2つの方程式の解の集合は、方程式のすべての解の集合である。 ${\displaystyle n_{i}}$${\displaystyle a_{1,2}}$

${\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}$

他の は互いに素なので、 k方程式の初期問題を解くことは、方程式の同様の問題に簡略化されます。このプロセスを繰り返すと、最終的に初期問題の解が得られます。 ${\displaystyle n_{i}}$${\displaystyle n_{1}n_{2},}$${\displaystyle k-1}$

解を構築するには、モジュライの数に関する帰納法を行う必要はありません。ただし、このような直接的な構築には大きな数での計算が多く必要になるため、効率が悪くなり、あまり使用されません。ただし、ラグランジュ補間はこの構築の特殊なケースであり、整数ではなく多項式に適用されます。

を1つを除くすべての法の積とします。 は互いに素であり、と は互いに素です。したがってベズー の恒等式が適用され、 と が存在し、${\displaystyle N_{i}=N/n_{i}}$${\displaystyle n_{i}}$${\displaystyle N_{i}}$${\displaystyle n_{i}}$${\displaystyle M_{i}}$${\displaystyle m_{i}}$

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

合同法の解は

${\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}$

実際、 はの 倍数なので、${\displaystyle N_{j}}$${\displaystyle n_{i}}$${\displaystyle i\neq j,}$

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

すべての${\displaystyle i.}$

合同のシステムを考えてみましょう:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}}$

ここで、 は互いに素であり、 とします。このセクションでは、 の一意の解を計算するためのいくつかの方法について説明します。 となる。これらの方法は、例に適用される。 ${\displaystyle n_{i}}$${\displaystyle N=n_{1}n_{2}\cdots n_{k}.}$${\displaystyle x}$${\displaystyle 0\leq x<N,}$

${\displaystyle {\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}.\end{aligned}}}$

計算方法にはいくつか種類があります。最初の 2 つは小さな例には便利ですが、積が大きい場合には非常に非効率的になります。3 つ目は、§ 存在 (構成的証明) で示した存在証明を使用します。積が大きい場合やコンピューター計算の場合に 最も便利です。${\displaystyle n_{1}\cdots n_{k}}$${\displaystyle n_{1}\cdots n_{k}}$

xの値が解であるかどうかを確認するのは簡単です。各n _iによるxのユークリッド除算の剰余を計算すれば十分です。したがって、解を見つけるには、解が見つかるまで 0からNまでの整数を順に確認すれば十分です。

この方法は非常に単純ですが、非常に非効率的です。ここで検討した単純な例では、解である39を見つけるために40 個の整数 ( 0を含む) をチェックする必要があります。入力のサイズは定数係数までNの桁数であり、平均演算回数はNのオーダーであるため、これは指数時間アルゴリズムです。

したがって、この方法は手書きの計算でもコンピューターでもほとんど使用されません。

ふるい分けによって解の探索は劇的に速くなる可能性がある。この方法では、一般性を失うことなく、（そうでない場合は、それぞれをで割った余りに置き換えるだけで十分である）と仮定する。これは、解が等差数列に属することを意味する。${\displaystyle 0\leq a_{i}<n_{i}}$${\displaystyle a_{i}}$${\displaystyle n_{i}}$

${\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }$

これらの数値を法としてテストすると、最終的に最初の2つの合同式の解が見つかります。その解は等差数列に属します。 ${\displaystyle n_{2},}$${\displaystyle x_{2}}$

${\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }$

これらの数値を法としてテストし、すべての法がテストされるまで続けると、最終的に解が得られます。 ${\displaystyle n_{3},}$

この方法は、法が降順で並べられている場合、つまり、例えば、次の計算が得られる場合、より高速になります。まず、4 を法として 5 (最大の法) と同値な数、つまり 4、9 = 4 + 5、14 = 9 + 5などを考えます。それぞれについて、4 (2 番目に大きい法) による余りを計算し、4 を法として 3 と同値な数になるまで続けます。次に、各ステップで20 = 5 × 4を加算し、3 による余りのみを計算します。これは次のようになります。 ${\displaystyle n_{1}>n_{2}>\cdots >n_{k}.}$

4 mod 4 → 0。続行

4 + 5 = 9 mod 4 →1。続行

9 + 5 = 14 mod 4 → 2。続行

14 + 5 = 19 mod 4 → 3。では、3を法とする余りを考え、そのたびに5 × 4 = 20を加算していきます。

19 mod 3 → 1. 続行

19 + 20 = 39 mod 3 → 0。さて、これが結果です。

この方法は、モジュライの積がそれほど大きくない手書きの計算には適しています。ただし、モジュライの積が非常に大きい場合は、他の方法よりもはるかに遅くなります。この方法は、体系的な検索よりも大幅に高速ですが、指数関数的な時間計算量があるため、コンピューターでは使用されません。

構成的存在証明によれば、2つのモジュライの場合、解はモジュライのベズー係数を計算し、続いてモジュロを法とする乗算、加算、および減算を数回行うことで得られる（${\displaystyle n_{1}n_{2}}$区間 内の結果を得るため）。ベズー係数は拡張ユークリッド互除法で計算できるため、全体の計算時間は最大で の2乗時間となる。ここで はの桁数を表す。${\displaystyle (0,n_{1}n_{2}-1)}$ ${\displaystyle O((s_{1}+s_{2})^{2}),}$${\displaystyle s_{i}}$${\displaystyle n_{i}.}$

2 つ以上のモジュラスの場合、2 つのモジュラスに対する方法により、任意の 2 つの合同式を、モジュラスの積を法とする 1 つの合同式に置き換えることができます。このプロセスを繰り返すと、最終的に、すべてのモジュラスの積の桁数の 2 乗の複雑さを持つソリューションが得られます。この 2 乗の時間複雑さは、モジュラスが再グループ化される順序に依存しません。最初の 2 つのモジュラスを再グループ化し、次に結果のモジュラスを次のモジュラスと再グループ化する、というように繰り返すことができます。この戦略は実装が最も簡単ですが、大きな数値を伴う計算も必要になります。

別の戦略は、モジュライを、積が（可能な限り）同等のサイズを持つペアに分割し、各ペアに 2 つのモジュライの方法を並列に適用し、近似的に 2 で割った数のモジュライで反復することです。この方法により、アルゴリズムの並列化が容易になります。また、基本操作に高速アルゴリズム（つまり、準線形時間で動作するアルゴリズム）を使用する場合、この方法は、計算全体を準線形時間で動作するアルゴリズムを提供します。

現在の例 (モジュラスが 3 つだけ) では、両方の戦略は同一であり、次のように機能します。

3と4の ベズーの恒等式は

${\displaystyle 1\times 4+(-1)\times 3=1.}$

これを存在証明の式に当てはめると、

${\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}$

最初の2つの合同式の解は、他の解は −9 に3 × 4 = 12の任意の倍数を加えることで得られる。これらの解のどれでも続けることができるが、解3 = −9 +12はより小さい（絶対値で）ため、おそらく計算がより簡単になる。

5と3×4=12のベズー恒等式は

${\displaystyle 5\times 5+(-2)\times 12=1.}$

同じ式を再度適用すると、問題の解決策が得られます。

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

他の解は、3 × 4 × 5 = 60の任意の倍数を加算することによって得られ、最小の正の解は−21 + 60 = 39です。

中国剰余定理によって解かれる合同式系は、線形ディオファントス方程式系として書き直すことができる。

${\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}$

ここで、未知の整数は であり、したがって、システムの行列をスミス標準形またはエルミート標準形に簡約するなど、このようなシステムを解くためのすべての一般的な方法は、中国剰余定理の解を見つけるために使用できます。ただし、より具体的な問題に一般的なアルゴリズムを使用する場合と同様に、このアプローチは、ベズーの恒等式を直接使用する前のセクションの方法よりも効率が低くなります。 ${\displaystyle x}$${\displaystyle x_{i}.}$

§ 記述では、中国剰余定理が、剰余、合同、環同型という 3 つの異なる方法で述べられています。剰余に関する記述は、一般に主イデアル領域には適用されません。剰余はそのような環では定義されないためです。ただし、他の 2 つのバージョンは主イデアル領域R上で意味をなします。つまり、「整数」を「領域の元」に、 をRに 置き換えるだけで十分です。このコンテキストでは、定理のこれら 2 つのバージョンは真です。なぜなら、証明 (最初の存在証明を除く) は、すべての主領域上で真であるユークリッドの補題とベズーの恒等式に基づいているためです。 ${\displaystyle \mathbb {Z} }$

しかし、一般に、この定理は存在定理に過ぎず、ベズーの恒等式の係数を計算するアルゴリズムがない限り、解を計算する方法は提供されません。

§ 定理の記述で与えられた剰余に関する記述は、いかなる主イデアル領域にも一般化できませんが、ユークリッド領域への一般化は簡単です。体上の一変数多項式は、整数ではないユークリッド領域の典型的な例です。したがって、体の環の場合について定理を述べま​​す。一般的なユークリッド領域の定理を得るには、次数をユークリッド領域の ユークリッド関数に置き換えるだけで十分です。${\displaystyle R=K[X]}$${\displaystyle K.}$

したがって、多項式の中国式剰余定理は次のようになります。（法）を、に対して、における互いに素な対多項式とします。を の次数、を の和とします。 が、任意のiに対してまたはとなる多項式である 場合、 となる多項式 は 1 つだけ存在し、をで除した余りは、任意のiに対して となります。 ${\displaystyle P_{i}(X)}$${\displaystyle i=1,\dots ,k}$${\displaystyle R=K[X]}$${\displaystyle d_{i}=\deg P_{i}}$${\displaystyle P_{i}(X)}$${\displaystyle D}$${\displaystyle d_{i}.}$${\displaystyle A_{i}(X),\ldots ,A_{k}(X)}$${\displaystyle A_{i}(X)=0}$${\displaystyle \deg A_{i}<d_{i}}$${\displaystyle P(X)}$${\displaystyle \deg P<D}$${\displaystyle P(X)}$${\displaystyle P_{i}(X)}$${\displaystyle A_{i}(X)}$

解の構築は、§ 存在（構成的証明）または§ 存在（直接証明）のように行うことができます。ただし、後者の構築は、次のように、拡張ユークリッドの互除法の代わりに部分分数分解を使用することで簡略化できます。

したがって、次の合同式を満たす 多項式を見つけたい。${\displaystyle P(X)}$

${\displaystyle P(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},}$

のために${\displaystyle i=1,\ldots ,k.}$

多項式を考えてみましょう

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}}$

の部分分数分解により、k次の多項式が得られる。 ${\displaystyle 1/Q(X)}$${\displaystyle S_{i}(X)}$${\displaystyle \deg S_{i}(X)<d_{i},}$

${\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {S_{i}(X)}{P_{i}(X)}},}$

そしてこうして

${\displaystyle 1=\sum _{i=1}^{k}S_{i}(X)Q_{i}(X).}$

すると、同時合同系の解は多項式で与えられる。

${\displaystyle \sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X).}$

実際、私たちは

${\displaystyle \sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},}$

のために${\displaystyle 1\leq i\leq k.}$

この解はより大きい次数を持つかもしれない。より小さい次数の唯一の解は、をユークリッド除算した余りを考慮することによって推定できる。この解は ${\displaystyle D=\sum _{i=1}^{k}d_{i}.}$${\displaystyle D}$${\displaystyle B_{i}(X)}$${\displaystyle A_{i}(X)S_{i}(X)}$${\displaystyle P_{i}(X).}$

${\displaystyle P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X).}$

多項式に対する中国剰余定理の特殊なケースはラグランジュ補間である。これについては、1次の k モニック多項式を考えてみよう。

${\displaystyle P_{i}(X)=X-x_{i}.}$

がすべて異なる場合、それらは互いに素です。多項式を で割った余りは、多項式剰余定理により、です。 ${\displaystyle x_{i}}$${\displaystyle P_{i}(X)}$${\displaystyle P(X)}$${\displaystyle P(x_{i})}$

ここで、を定数（次数0の多項式）とします。ラグランジュ補間と中国剰余定理は、次数0未満の唯一の多項式の存在を主張しており、 ${\displaystyle A_{1},\ldots ,A_{k}}$${\displaystyle K.}$${\displaystyle P(X),}$${\displaystyle k}$

${\displaystyle P(x_{i})=A_{i},}$

すべての${\displaystyle i.}$

ラグランジュ補間公式は、この場合、まさに上記の解の構築の結果である。より正確には、

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}$

の部分分数分解は ${\displaystyle {\frac {1}{Q(X)}}}$

${\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}$

実際、右辺を共通分母にすると、

${\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}$

分子は1に等しく、これは次数以下の多項式であり、異なる値に対して1の値を取る。${\displaystyle k,}$${\displaystyle k}$${\displaystyle X.}$

上記の一般的な式を使用すると、ラグランジュ補間式が得られます。

${\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}$

エルミート補間は、任意の次数の係数を含む可能性がある一変数多項式に対する中国剰余定理の応用です (ラグランジュ補間には次数 1 の係数のみが含まれます)。

この問題は、多項式とその一次導関数がいくつかの固定点で与えられた値を取るような、可能な限り最小の次数の多項式を見つけることです。

より正確には、基底体の要素をとし、を における求める多項式の1 次導関数の値とします（多項式自体の値である 0 次導関数を含む）。問題は、およびに対してj次導関数がで 値を取る多項式を見つけることです。${\displaystyle x_{1},\ldots ,x_{k}}$${\displaystyle k}$ ${\displaystyle K,}$${\displaystyle i=1,\ldots ,k,}$${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$${\displaystyle r_{i}}$${\displaystyle x_{i}}$${\displaystyle P(X)}$${\displaystyle a_{i,j}}$${\displaystyle x_{i},}$${\displaystyle i=1,\ldots ,k}$${\displaystyle j=0,\ldots ,r_{j}.}$

多項式を考える

${\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}$

これは、未知の多項式の における次数のテイラー多項式である。したがって、 ${\displaystyle r_{i}-1}$${\displaystyle x_{i}}$${\displaystyle P(X).}$

${\displaystyle P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.}$

逆に、これらの合同性を満たす任意の多項式は、特に任意の${\displaystyle P(X)}$${\displaystyle k}$${\displaystyle i=1,\ldots ,k}$

${\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}$

したがって、はにおけるのテイラー多項式であり、つまり、初期のエルミート補間問題を解きます。中国剰余定理は、 の合計よりも小さい次数の多項式が正確に 1 つ存在し、これらの合同性を満たすことを主張しています。 ${\displaystyle P_{i}(X)}$${\displaystyle r_{i}-1}$${\displaystyle x_{i}}$${\displaystyle P(X)}$${\displaystyle r_{i},}$${\displaystyle k}$

解を計算する方法はいくつかあります。§ 単変数多項式環とユークリッド領域上での冒頭で説明した方法を使用できます。§ 存在 (構成的証明) または § 存在 (直接証明) に示されている構成を使用することもできます。 ${\displaystyle P(X).}$

中国剰余定理は互いに素でない法に一般化できます。を任意の整数、、とし、合同法のシステムを考えます。 ${\displaystyle m,n,a,b}$${\displaystyle g=\gcd(m,n)}$${\displaystyle M=\operatorname {lcm} (m,n)}$

${\displaystyle {\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}}$

の場合、このシステムには を法とする一意の解が存在します。それ以外の場合、解は存在しません。 ${\displaystyle a\equiv b{\pmod {g}}}$${\displaystyle M=mn/g}$

ベズーの等式を使ってと書くと、解は次のように与えられる。 ${\displaystyle g=um+vn}$

${\displaystyle x={\frac {avn+bum}{g}}.}$

これは整数を定義します。gはmとnの両方を割り切れるからです。それ以外は、証明は互いに素な法の証明と非常に似ています。^[16]

中国剰余定理は、互いに素なイデアル（共最大イデアルとも呼ばれる）を使用することで、任意の環 に一般化できます。2つのイデアルIとJが互いに素とは、と が存在し、となる場合です。この関係は、この一般化に関連する証明においてベズーの恒等式の役割を果たしますが、それ以外は非常に似ています。一般化は次のように述べられます。^{[17] [18]} ${\displaystyle i\in I}$${\displaystyle j\in J}$${\displaystyle i+j=1.}$

I ₁ , ..., I _{k を}環の両側イデアルとし、I をそれらの共通部分とします。イデアルが互いに素である場合、同型性が得られます。 ${\displaystyle R}$

${\displaystyle {\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}}$

商環 との直積の間の である。 ここで「 」はイデアルによって定義される商環の元の像を表す。 さらに、が可換である場合、互いに素なイデアルのイデアル交差はそれらの積に等しい。つまり、 ${\displaystyle R/I}$${\displaystyle R/I_{i},}$${\displaystyle x{\bmod {I}}}$${\displaystyle x}$${\displaystyle I.}$${\displaystyle R}$

${\displaystyle I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},}$

すべてのi ≠ jについて、 I _iとI _{j が}互いに素である場合。

とが互いに素な2辺イデアルであるとする。 ${\displaystyle I_{1},I_{2},\dots ,I_{k}}$${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

は上で定義した同型写像とする。はi番目だけが1 である以外すべての要素が0であるの元とし、${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

は、互いに直交する中心冪等元である。これは特に、任意のiおよびjに対して、かつが成り立つことを意味する。さらに、かつ${\displaystyle e_{i}}$${\displaystyle e_{i}^{2}=e_{i}}$${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$${\textstyle e_{1}+\cdots +e_{n}=1,}$${\displaystyle I_{i}=R(1-e_{i}).}$

要約すると、この一般化された中国剰余定理は、交差がゼロである互いに素な2辺イデアルを与えることと、合計が1になる中心および2つの直交冪等性を与えることとの間の同値である。^[19]

中国剰余定理は、ゲーデルの不完全性定理の証明に関係する、数列のゲーデル番号付けを構築するために使用されてきた。

素因数FFT アルゴリズム(グッド・トーマス アルゴリズムとも呼ばれる) は、中国剰余定理を使用して、サイズの高速フーリエ変換の計算を、より小さいサイズと(とが互いに素である場合)の 2 つの高速フーリエ変換の計算に削減します。 ${\displaystyle n_{1}n_{2}}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$${\displaystyle n_{1}}$${\displaystyle n_{2}}$

RSA のほとんどの実装では、 HTTPS証明書の署名時および復号化時 に中国剰余定理が使用されます。

中国剰余定理は秘密分散法にも応用できます。秘密分散法とは、ある一組のシェアを複数の人々に配布し、そのグループ全員が（一人ではなく）一緒にその一組のシェアからある秘密を復元できるようにすることです。各シェアは合同式で表され、中国剰余定理を使用した合同式の解が復元すべき秘密です。中国剰余定理を使用した秘密分散法は、中国剰余定理とともに、特定の濃度未満のシェアの集合から秘密を復元することが不可能であることを保証する特別な整数列を使用します。

中パルス繰り返し周波数レーダーで使用される距離の曖昧さを解決する技術は、中国剰余定理の特殊なケースとして考えることができます。

有限アーベル群の全射 が与えられた場合、中国剰余定理を用いてそのような写像の完全な記述を与えることができる。まず、定理は同型を与える。 ${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$

${\displaystyle {\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}$

ここで。さらに、任意の誘導写像 ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$

${\displaystyle \mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}}$

元の全射から、 となり、素数のペアに対して、ゼロでない全射は ${\displaystyle a_{k}\geq b_{l}}$${\displaystyle p_{n_{k}}=p_{m_{l}},}$ ${\displaystyle p,q}$

${\displaystyle \mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}}$

およびの場合に定義できます。 ${\displaystyle p=q}$${\displaystyle a\geq b}$

これらの観察は、そのようなすべての写像の 逆極限として与えられる、profinite 整数の環を構成するために極めて重要です。

デデキントの文字の線型独立性に関する定理。Mをモノイド、k を整域とし、k上の乗法を考慮してモノイドとして見た場合、異なるモノイド準同型f _i  : M → kの任意の有限族(  f _i  ) _{i ∈ I}は線型独立である。言い換えると、次を満たす 元α _i ∈ kの族( α _i ) _{i ∈ Iはすべて、}  

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

族(0) _{i ∈ I}と等しくなければならない。

証明。まずkが体であると仮定し、そうでなければ、整域k をその商体で置き換えても何も変わりません。モノイド準同型f _i  : M → kをk代数準同型F _i  : k [ M ] → kに線形拡張できます。ここでk [ M ]はk上のMのモノイド環です。すると、線形性により、条件  

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}$

収穫

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

次に、 i、j ∈ I ; i ≠ jに対して、2つのk線型写像F _i  : k [ M ] → kとF _j  : k [ M ] → k は互いに比例しません。そうでなければ、f _iとf _jも比例し、したがって等しいことになります。なぜなら、モノイド準同型として、 f _i  (1) = 1 =   f _j  (1)を満たすためです。これは、これらが異なるという仮定と矛盾します。      

したがって、核 Ker  F _iとKer  F _jは異なる。k [ M ]/Ker  F _i ≅ F _i  ( k [ M ]) = kは体なので、Ker F _iはIの任意のiに対してk [ M ]の極大イデアルである。これらは異なり、かつ極大であるため、 i ≠ jのときは常にイデアルKer  F _iとKer  F _{j は}互いに素である。中国剰余定理 (一般環の場合) は同型性をもたらす。

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

どこ

${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

その結果、地図

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

は全射である。同型k [ M ]/Ker  F _i → F _i  ( k [ M ]) = kのもとで、写像Φ は以下に対応する。

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

今、

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

収穫

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

写像ψの像における任意のベクトル( u _i ) _{i ∈ I}に対して。ψ は射影的であるため、これは次のことを意味する。

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

あらゆるベクトルに対して

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

したがって、( αi ) _i∈I = (0 _{) i∈Iとなる。QED .}

• カバーシステム
• ハッセ原理
• 残基数システム

• Dauben, Joseph W. (2007)、「第 3 章: 中国の数学」、Katz, Victor J. (編)、『エジプト、メソポタミア、中国、インド、イスラムの数学: 資料集』、プリンストン大学出版、pp. 187–384、ISBN 978-0-691-11485-9
• デンス、ジョセフ・B.; デンス、トーマス・P. (1999)、数論の要素、アカデミック・プレス、ISBN 9780122091308
• Duchet、Pierre (1995)、「Hypergraphs」、グラハム、RL。グレッチェル、M. ; Lovász、L. (編)、Handbook of combinatorics、Vol. 1、2、アムステルダム: エルゼビア、381–432 ページ、MR  1373663特にセクション2.5「Helly Property」の393～394ページを参照してください。
• ガウス、カール・フリードリヒ（1986）、Disquisitiones Arithemeticae、アーサー・A・クラーク訳（第2版、訂正版）、ニューヨーク：シュプリンガー、ISBN 978-0-387-96254-2
• アイルランド、ケネス、ローゼン、マイケル（1990）、現代数論への古典的入門（第2版）、シュプリンガー・フェアラーク、ISBN 0-387-97329-X
• Kak、Subhash (1986)、「Aryabhata アルゴリズムの計算側面」(PDF)、Indian Journal of Science of Science、21 (1): 62–71
• カッツ、ビクター J. (1998)、数学の歴史 / 入門(第 2 版)、アディソン ウェスリー ロングマン、ISBN 978-0-321-01618-8
• リブレヒト、ウルリッヒ（1973）『13世紀の中国の数学：秦秋韶の「書書秋章」』ドーバー出版、ISBN 978-0-486-44619-6
• オーレ、オイステイン（1952）、「一般中国剰余定理」、アメリカ数学月刊誌、59（6）：365-370、doi：10.2307/2306804、JSTOR  2306804、MR  0048481
• オーレ、オイステイン（1988）[1948]、数論とその歴史、ドーバー、ISBN 978-0-486-65620-5
• Pisano、Leonardo (2002)、Fibonacci's Liber Abaci、Sigler、Laurence E. 訳、Springer-Verlag、pp. 402–403、ISBN 0-387-95419-8
• ローゼン、ケネス H. (1993)、初等数論とその応用(第 3 版)、Addison-Wesley、ISBN 978-0201-57889-8
• セングプタ、アンバー・N. (2012)、有限群の表現、半単純入門、Springer、ISBN 978-1-4614-1232-8
• ブルバキ、N. (1989)、代数 I、スプリンガー、ISBN 3-540-64243-9

• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001)、アルゴリズム入門(第 2 版)、MIT Pressおよび McGraw-Hill、ISBN 0-262-03293-7セクション31.5「中国剰余定理」、873～876ページを参照。
• 丁 鄭生、裴 丁一、サロマ、アルト (1996)、中国剰余定理: コンピューティング、コーディング、暗号化への応用、World Scientific Publishing、pp. 1–213、ISBN 981-02-2827-9
• ハンガーフォード、トーマス W. (1974)、代数学、大学院数学テキスト、第 73 巻、シュプリンガー出版、pp. 131-132、ISBN 978-1-4612-6101-8
• クヌース、ドナルド(1997)、『コンピュータプログラミングの技法』第 2 巻:半数値アルゴリズム(第 3 版)、Addison-Wesley、ISBN 0-201-89684-2セクション4.3.2（286～291ページ）、演習4.6.2～3（456ページ）を参照してください。

• 「中国剰余定理」、数学百科事典、EMS Press、2001 [1994]
• ワイスシュタイン、エリック W.、「中国剰余定理」、MathWorld
• PlanetMathの中国剰余定理。
• 孫子算経全文（中国語） – 中国語テキストプロジェクト