中國剩餘定理計算機

歡迎使用中國剩餘定理計算機，這是一個強大的數論工具，可使用中國剩餘定理 (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\)，使用擴展歐幾里得演算法找到 \(y_i\)，使得 \(M_i \cdot y_i \equiv 1 \pmod{m_i}\)。由於 \(M_i\) 與 \(m_i\) 互質（所有模數均兩兩互質），因此該反元素必定存在。

步驟 4：構造解

一般解為 \(x + k \cdot M\)，其中 \(k\) 為任何整數，這意味著解每隔 \(M\) 個整數重複一次。

如何使用本計算機

1. 輸入您的同餘式： 對於每個方程式 \(x \equiv a \pmod{m}\)，輸入餘數 \(a\) 和模數 \(m\)。從 2 個同餘式開始，點擊「添加同餘式」可增加更多（最多 10 個）。
2. 檢查您的模數： 所有模數必須為大於等於 2 的正整數，且兩兩互質。計算機將自動驗證這一點。
3. 點擊「求解方程組」： 計算機應用 CRT 演算法，顯示唯一解以及逐步運算過程。
4. 查看視覺化展示： 數線顯示了來自每個方程式的同餘類別如何在解的位置相交。
5. 驗證： 驗證部分確認了該解滿足每一個原始同餘式。

理解結果

• 最小非負整數解 (x₀)： 範圍在 [0, M−1] 之間的唯一解
• 一般解： 形式為 x₀ + kM 的所有整數，其中 k 為任何整數
• 驗證表： 確認每個同餘式滿足 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（更一般地說，為 23 + 105k，其中 k 為任何非負整數）。

何時不適用 CRT？

• 非互質模數： 如果任何一對模數共享大於 1 的公因數，則標準 CRT 不保證有解。如果餘數兼容，解可能仍然存在，但本計算機要求模數兩兩互質以使用標準演算法。
• 單個同餘式： CRT 需要至少 2 個同餘式。單個同餘式 \(x \equiv a \pmod{m}\) 已經有顯而易見的解 x = a。

擴展歐幾里得演算法

擴展歐幾里得演算法 對於 CRT 至關重要，因為它用於尋找模反元素。給定整數 \(a\) 和 \(b\)，它能找到整數 \(x\) 和 \(y\) 使得：

當 \(\gcd(a, b) = 1\) 時，\(x\) 即為 \(a\) 模 \(b\) 的模反元素，即 \(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。一般解為 x + k×M，其中 k 為任何整數。

中國剩餘定理有哪些應用？

CRT 有許多實際應用：RSA 密碼學使用 CRT 進行高效解密。電腦科學使用它透過將計算分解為較小的模數部分來進行大數運算。信號處理將 CRT 應用於更正錯誤碼。事件以不同間隔重複的排程和日曆問題也會用到 CRT。

如果模數不是互質會怎樣？

如果模數不是兩兩互質，則標準 CRT 不能直接適用。在某些情況下，如果滿足特定的兼容性條件（餘數在非互質模數的最大公因數下必須一致），解可能仍然存在。然而，如果不存在解，則該同餘方程組是不一致的。

其他資源

• 中國剩餘定理 - 維基百科
• 擴展歐幾里得演算法 - 維基百科
• 同餘運算 - 維基百科