中国の剰余定理計算機：剰余体系をステップバイステップで解く

中国の剰余定理とは何か？

中国の剰余定理（CRT）は、連立合同式x ≡ a₁ (mod m₁)、x ≡ a₂ (mod m₂)、...、x ≡ aₙ (mod mₙ)があり、法数m₁、m₂、...、mₙが互いに素である（すべてのペアが1以外の共通因数を持たない）場合、xに対してM = m₁ × m₂ × ... × mₙを法とした解が正確に1つ存在することを述べています。この定理は、3世紀から5世紀の中国のテキスト『孫子算経』（孫の算術マニュアル）に最初に登場することからその名前が付けられ、そこで古典的なパズルが提示されます：3で割ると余り2になり、5で割ると余り3になり、7で割ると余り2になる数を見つけるというものです。このパズル（そしてそれを解くCRTメソッド）は教室の外で常に現れています：RSA暗号化はCRTを使用して、1つの巨大な法数の代わりにより小さい法数で計算することで復号化を高速化し、コンピュータサイエンティストは大きな数をより小さい剰余のタプルとして表現して高速演算を行い、暦システムは異なる長さのサイクル（曜日、月の日数、閏年サイクル）を調和させるために使用します。

中国の剰余定理：互いに素な法数m₁、...、mₙに対して、連立式x ≡ aᵢ (mod mᵢ)はM = m₁ × m₂ × ... × mₙを法とした解が正確に1つ存在します。

中国の剰余定理計算機はどのように機能するのか？

中国の剰余定理計算機は、特に法数が3つ以上ある場合に手動で追跡するのが退屈な4つのステージを自動化します。特に剰余逆元の計算が重要です。内部的には、各合同式をペア（aᵢ、mᵢ）として扱い、法数が一緒に使用可能であることを確認し、試行錯誤ではなく加重和を使用してユニークな解を構築します。これら4つのステージを理解することで、計算機の出力を検証するか、計算機が許可されていない試験で同じ問題を手作業で解くことができます。

すべての中国の剰余定理計算機の背後にある公式：x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M、ここでMᵢ = M/mᵢ、yᵢはMᵢのmᵢを法とした逆元です。

法数が互いに素かどうかをどのように確認するか？

中国の剰余定理の教科書的なバージョンは互いに素な法数を必要とします。しかし、実際のシステム（特にスケジューリングや暗号化の問題に現れるもの）は、因数を共有する法数を持つことがよくあります。一般化されたCRTバージョンは依然として適用されますが、システムが最初に互いに素性の確認に合格した場合のみです。合同式x ≡ aᵢ (mod mᵢ)とx ≡ aⱼ (mod mⱼ)のすべてのペアに対して、2つは重複部分で一致する必要があります。つまり、aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))です。たとえ1つのペアでこのチェックが失敗した場合でも、システムは完全に解がなく、どのような他の情報があっても間違った数を返す代わりに良い計算機がこれを報告します。

互いに素でない法数の互いに素性ルール：x ≡ aᵢ (mod mᵢ)とx ≡ aⱼ (mod mⱼ)の両方が真である場合のみ、aᵢ ≡ aⱼ (mod gcd(mᵢ、mⱼ))を満たす場合のみです。

剰余逆元とは何か、そしてどのようにして見つけるか？

法mを法とする数aの剰余逆元は、a × b ≡ 1 (mod m)を満たす別の数bです。これは通常の除算での1/aと同じ役割を果たしますが、固定された法数内の全数に限定されます。剰余逆元が存在するのは、gcd(a、m) = 1の場合のみです。これは、標準的な中国の剰余定理が互いに素な法数を必要とする理由です：すべてのMᵢがmᵢを法とした逆元を持つことを保証します。手作業で剰余逆元を見つける最も信頼できる方法は、拡張ユークリッド互除法です。これは通常のgcdアルゴリズムを前進させ、次に逆行して1をaとmの組み合わせとして表現します。

小さい法数の場合、候補を直接テストする方が速いことがよくあります：aに1、2、3、...をmを法として乗算して、積が1になるまで繰り返します。より大きい法数では、拡張ユークリッド互除法が遥かに信頼できます。

演習例：互いに素な合同式を解く

これは古い孫子算経の問題です：x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)を満たすxを見つけます。法数3、5、7は互いに素であるため、標準的なCRT公式が直接適用されます。

x ≡ 23 (mod 105)—中国の剰余定理計算機が即座に返す同じ答えで、1,000年以上前にこの数学分野を開いたのと同じパズルです。

演習例：互いに素でない法数を調和させる

次に、x ≡ 3 (mod 4)とx ≡ 1 (mod 6)を解きます。4と6は互いに素ではなく（2の因数を共有します）。互いに素な法数の例の標準公式は直接は適用されませんが、最初に互いに素性の確認に合格したシステムは、依然として法数の最小公倍数を法とした唯一の解を持つことができます。

法数が共通因数を共有する場合、互いに素な法数公式をそのまま使用することはできません。逆元を見つける前に結果の合同式をgcd(mᵢ、mⱼ)で除く必要があります。さもなければ逆元は存在しません。

最小の非負解を再構成する

互いに素性の確認に合格したすべての中国の剰余定理システムは、1つではなく無限に多くの整数解を持ちます。しかし、それらはすべてMを法としてお互いに合同です（または互いに素でない場合はlcm(m₁、...、mₙ)を法とした場合）。慣例として、計算機はその無限ファミリーの最小の非負代表である値x₀（0 ≤ x₀ < Mを満たす）を報告します。なぜなら、それは述べ、比較、検証するのが最も簡単な単一の正規答えだからです。他のすべての解はx₀にMの倍数を加算または減算したものです。

最小の非負解を再構成する

各ステップは以下の通りです：

負の値または過度にサイズが大きい中間結果は間違っていません。Mの倍数を加算または減算して、値が[0、M)に入るまでにしてください。

中国の剰余定理の最も一般的な間違いは何か？

CRT問題のほとんどのエラーは、最終的な計算の欠陥ではなく、確認をスキップすることから発生します。これが、問題の最後ではなく最初で減速する価値がある理由です。

あなたの答えが元の各合同式に戻して接続されていない場合、互いに素性の確認と剰余逆元を最初に再チェックしてください。そこで、ほぼすべてのCRT間違いが実際に発生します。

練習問題：中国の剰余定理計算機スキルをテストする

以下の3つのシステムに手作業で取り組み、互いに素性または互いに素性を最初にチェックしてから、以下の解と比較してください。2番目の問題は意図的に解不可能です—これを認識することは、解が存在する場合に数値答えを見つけることと同じくらい重要です。

中国の剰余定理と真の流暢性を構築する最速の方法は、互いに素、互いに素でない—だが互いに素、および互いに素でないシステムの混合を解くことです。どのケースにいるかを認識することはスキルの半分です。