中国剰余定理電卓

中国剰余定理電卓へようこそ。これは、中国剰余定理（CRT）を使用して連立一次合同式を解く強力な数論ツールです。剰余算を学習している学生、数学オリンピックの準備をしている方、暗号技術に取り組んでいる方、あるいは単に数論を探索している方であっても、この電卓は一意の解において各剰余類がどのように整列するかを示すインタラクティブな視覚化とともに、完全なステップバイステップの解決策を提供します。

中国剰余定理とは何ですか？

中国剰余定理 (Chinese Remainder Theorem, CRT) は、法が対ごとに互いに素である場合に、連立合同式の解の存在と一意性を保証する数論の基本的な結果です。この定理は、紀元3世紀頃に中国の数学者である孫子によって、その著書『孫子算経』の中で最初に記述されました。

形式的には、以下のシステムが与えられたとき：

すべての法 \(m_1, m_2, \ldots, m_k\) が対ごとに互いに素（すなわち、すべての \(i \neq j\) に対して \(\gcd(m_i, m_j) = 1\)）である場合、法 \(M = m_1 \times m_2 \times \cdots \times m_k\) において一意の解 \(x\) が存在します。

CRTアルゴリズムの仕組み

この電卓で使用されているアルゴリズムの構成的な証明は以下の通りです：

ステップ 1: M を計算する

すべての法の積を計算します：

ステップ 2: 各 Mᵢ を計算する

各合同式 \(i\) について、\(M_i = M / m_i\) を計算します。これは、\(m_i\) を除くすべての法の積です。

ステップ 3: モジュラ逆元を求める

各 \(i\) について、拡張ユークリッド互除法を使用して \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) となる \(y_i\) を見つけます。\(M_i\) と \(m_i\) は互いに素（すべての法が対ごとに互いに素であるため）なので、この逆元は常に存在します。

ステップ 4: 解を構築する

一般解は、任意の整数 \(k\) に対して \(x + k \cdot M\) です。これは、解が整数 \(M\) ごとに繰り返されることを意味します。

この電卓の使い方

1. 合同式を入力する： 各方程式 \(x \equiv a \pmod{m}\) について、剰余 \(a\) と法 \(m\) を入力します。最初は2つの合同式から始まり、「合同式を追加」をクリックして増やすことができます（最大10個まで）。
2. 法を確認する： すべての法は2以上の正の整数であり、かつ対ごとに互いに素である必要があります。電卓はこれを自動的に検証します。
3. 「連立方程式を解く」をクリック： 電卓はCRTアルゴリズムを適用し、ステップバイステップの作業過程とともに一意の解を表示します。
4. 視覚化を確認する： 数直線は、各方程式の剰余類が解の位置でどのように交差するかを示します。
5. 検証： 検証セクションでは、解が元のすべての合同式を満たしていることを確認します。

結果の理解

• 最小の非負の解 (x₀): [0, M−1] の範囲における一意の解です。
• 一般解: k を任意の整数としたときの x₀ + kM の形式のすべての整数です。
• 検証テーブル: 各合同式に対して x₀ mod mᵢ = aᵢ であることを確認します。
• ステップバイステップの内訳: 各方程式の Mᵢ、モジュラ逆元 yᵢ、および部分和 aᵢ·Mᵢ·yᵢ を示します。
• 数直線: 剰余類が解においてどのように整列するかを視覚的に表現したものです。

中国剰余定理の応用例

古典的な孫子の問題

『孫子算経』にある元の問題は次のようなものです：「今、物がいくつかあるが、その数はわからない。三つずつ数えると二つ余り、五つずつ数えると三つ余り、七つずつ数えると二つ余る。物はいくつあるか。」

これは次のように翻訳されます：\(x \equiv 2 \pmod{3}\)、\(x \equiv 3 \pmod{5}\)、\(x \equiv 2 \pmod{7}\)。CRTを使用すると、答えは x = 23 となります（より一般的には、任意の非負整数 k に対して 23 + 105k）。

CRTが適用されない場合

• 法が互いに素でない場合： 法のいずれかのペアが1より大きい共通の因数を持つ場合、標準的なCRTは解を保証しません。剰余に互換性があれば解が存在することもありますが、この電卓の標準アルゴリズムでは、法が対ごとに互いに素である必要があります。
• 単一の合同式： CRTには少なくとも2つの合同式が必要です。単一の合同式 \(x \equiv a \pmod{m}\) は、すでに自明な解 x = a を持っています。

拡張ユークリッド互除法

拡張ユークリッド互除法は、モジュラ逆元を求めるためにCRTに不可欠です。整数 \(a\) と \(b\) が与えられたとき、次を満たす整数 \(x\) と \(y\) を見つけます：

\(\gcd(a, b) = 1\) のとき、\(x\) は \(b\) を法とする \(a\) のモジュラ逆元、すなわち \(a \cdot x \equiv 1 \pmod{b}\) となります。

よくある質問

中国剰余定理とは何ですか？

中国剰余定理（CRT）は、すべての法が対ごとに互いに素である場合、連立合同式 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ) に対して、法 M = m₁ × m₂ × ... × mₖ において一意の解が存在するという定理です。この定理は、3世紀に中国の数学者である孫子によって最初に記述されました。

「対ごとに互いに素」とはどういう意味ですか？

対ごとに互いに素とは、法のすべてのペアが1以外の共通因数を持たないことを意味します。例えば、{3, 5, 7} は gcd(3,5)=1, gcd(3,7)=1, gcd(5,7)=1 であるため対ごとに互いに素です。しかし、{4, 6, 5} は gcd(4,6)=2 であるため、対ごとに互いに素ではありません。

連立合同式をステップバイステップで解くにはどうすればよいですか？

CRTを使用して解く手順：(1) すべての法が対ごとに互いに素であることを確認します。(2) すべての法の積 M を計算します。(3) 各合同式について、Mᵢ = M/mᵢ を計算します。(4) 拡張ユークリッド互除法を使用して、mᵢ を法とする Mᵢ の逆元 yᵢ を見つけます。(5) 解 x = Σ(aᵢ × Mᵢ × yᵢ) mod M を計算します。一般解は任意の整数 k に対して x + k×M です。

中国剰余定理の応用例は何ですか？

CRTには多くの実用的な応用があります：RSA暗号では効率的な復号に使用されます。コンピュータサイエンスでは、計算を小さなモジュラー部分に分割することで大きな数の算術に使用されます。信号処理では誤り訂正符号に、またイベントが異なる間隔で繰り返されるスケジューリングやカレンダーの問題にも使用されます。

法が互いに素でない場合はどうなりますか？

法が対ごとに互いに素でない場合、標準的な中国剰余定理は直接適用されません。特定の適合条件が満たされる場合（剰余が非互いに素な法の最大公約数において矛盾しない場合）、解が存在することもあります。しかし、解が存在しない場合、その連立合同式は矛盾しています。

追加リソース

• 中国剰余定理 - Wikipedia
• 拡張ユークリッド互除法 - Wikipedia
• 剰余類と合同式 - Wikipedia