中国の余剰定理とは？
ちゅうごくのよじょうていり
「定理」の用語まとめを見る中国の余剰定理とは、互いに素な複数の整数による余りの条件から、元の整数を一意に決定できるという数論の定理です。
中国の余剰定理（Chinese Remainder Theorem、CRT）とは、互いに素な正の整数m₁、m₂、…、mₙに対して、それぞれを法とする余りの条件（x ≡ a₁ (mod m₁)、x ≡ a₂ (mod m₂)、…）を同時に満たす整数xが、m₁×m₂×…×mₙを法として一意に存在するという定理です。
その名称は、古代中国の数学書『孫子算経』（4〜5世紀頃）に類似した問題が登場することに由来します。「今、兵士の数を知りたいが、3で割ると2余り、5で割ると3余り、7で割ると2余る。兵士は何人か？」という形式の問題です。
この定理が重要な理由は多岐にわたります。
- 暗号理論：RSA暗号の計算高速化（CRT-RSA）に利用される
- コンピューター演算：大きな数の演算を複数の小さな法での演算に分割して並列処理できる
- スケジューリング問題：周期的な条件が重なる日時を求める計算に応用できる
- 符号理論・信号処理：多項式環での演算にも拡張される
中国の余剰定理は抽象代数学においても環論の重要な命題として一般化されており、整数論を超えて現代数学・情報科学の基盤となっています。
使い方・例文
「3で割ると1余り、5で割ると2余る整数は何か？」という問いに、中国の余剰定理を使うと15以下の範囲でその整数が7であることを体系的に求めることができます。
この用語をシェア
最終更新: