中国剰余定理

About simultaneous modular congruences

数学において、中国剰余定理は、整数nを複数の整数でユークリッド的に割ったときの余りがわかっていれば、これらの整数の積でnを割ったときの余りを、約数が互いに素である（2つの約数が1以外の共通因数を持たない）という条件の下で一意に決定できるというものである。 ^[1]

孫子の元の定式化：x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) 解は x = 23 + 105 k（ kは整数）

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

nを 3 で割った余りが2、 nを 5 で割った余りが3、nを 7 で割った余りが 2 であることが分かっている場合、他の情報がなくても、 nの値が分からなくても、 nを105 で割った余り（3、5、7 の積）を計算できます。この例では、余りは 23 です。さらに、この余りは、 nが105 未満の唯一の正の値です。

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

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

歴史

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

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

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

中国の剰余定理は、ガウスの 1801 年の著書『Disquisitiones Arithmeticae』に登場します。^[9]

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

声明

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}}}$

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

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

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

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

${\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を法とする整数環の直積との間の関係。これは、一連の算術演算を1つずつ行う場合、それぞれにおいて独立に同じ計算を行い、その後、同型性（右から左へ）を適用することで結果を得ることができることを意味します。Nと演算回数が多い場合、これは直接計算よりもはるかに高速になる可能性があります。これは、マルチモジュラ計算という名前で、整数または有理数上の線型代数において広く使用されています。 ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ ${\displaystyle \mathbb {Z} /n_{i}\mathbb {Z} }$

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

証拠

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

ユニークさ

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の明示的な構成によって確立される。^[16]この構成は2つのステップに分けられ、まず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方程式は互いに素であるため、 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の値が解であるかどうかは簡単に確認できます。xを各n _iでユークリッド除算した余りを計算すれば十分です。したがって、解を求めるには、 0からNまでの整数を解が見つかるまで順に調べていくだけで十分です。

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

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

ふるい分けで検索

ふるいを使って求めた中国剰余定理問題の元の定式化の最小の2つの解、23と128

ふるい分けによって解の探索は劇的に高速化される可能性がある。この手法では、一般性を失うことなく、 と仮定する（そうでない場合は、各 をで割った余りに置き換えれば十分である）。これは、解が等差数列に属することを意味する。 ${\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},}$

この方法は、法が降順で並べられている場合、つまり、例えば、以下の計算式が得られる。まず、5（最大の法）を法として4と合同な数、つまり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次導関数がいくつかの固定点で所定の値を取るような、可能な限り最小の次数の多項式を見つけることです。

より正確には、基底体の元をとし、を における求める多項式の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の両方を割り切るからである。それ以外の点では、証明は互いに素な法の証明と非常に似ている。^[17]

任意の環への一般化

中国剰余定理は、互いに素なイデアル（共最大イデアルとも呼ばれる）を用いることで、任意の環に一般化できる。2つのイデアルIとJが互いに素とは、 と が存在し、となる場合である。この関係は、この一般化に関連する証明においてベズーの恒等式の役割を果たすが、それ以外は他の証明は非常によく似ている。この一般化は以下のように述べられる。^{[18] [19]} ${\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が互いに素である場合。

べき等性による解釈

とが互いに素な両側イデアルであるとする。 ${\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}).}$

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

アプリケーション

シーケンス番号

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

高速フーリエ変換

素因数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は体なので、Iの任意のiに対してKer F _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。

参照

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

注記

1. 「DLMF: §27.15 中国剰余定理 ‣ 応用 ‣ 第27章 数論の関数」dlmf.nist.gov . 2025年1月31日閲覧。
2. カッツ 1998、197ページ
3. デンス＆デンス 1999、156ページ
4. ダウベン 2007、302ページ
5. カク 1986
6. ピサーノ 2002, 402–403ページ
7. ダウベン 2007、310ページ
8. リブレヒト 1973
9. ガウス 1986、第32～36条
10. アイルランド＆ローゼン 1990、36ページ
11. オーレ 1988、247ページ
12. オーレ 1988、245ページ
13. アイルランド＆ローゼン 1990、34ページ
14. アイルランド＆ローゼン 1990、35ページ
15. デュシェ 1995
16. ローゼン 1993、136ページ
17. 1952年鉱石。
18. アイルランド＆ローゼン 1990、181ページ
19. セングプタ 2012、313ページ
20. ブルバキ、N. 1989、110ページ

参考文献

• ダウベン、ジョセフ・W.（2007）、「第3章：中国の数学」、カッツ、ビクター・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版）』、アディソン・ウェスレー、ISBN 978-0201-57889-8
• セングプタ、アンバー・N.（2012）、有限群の表現、半単純入門、シュプリンガー、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-731.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プレス、2001 [1994]
• ワイススタイン、エリック・W.、「中国剰余定理」、MathWorld
• PlanetMathの中国剰余定理。
• 孫子算経全文（中国語） – 中国テキストプロジェクト

Retrieved from "https://en.wikipedia.org/w/index.php?title=Chinese_remainder_theorem&oldid=1315812949"