中文剩餘定理計算器：逐步求解模同餘系統
中文剩餘定理計算器透過將多個同餘方程組合成單個同餘方程來解決這些方程組 — 例如 x ≡ 2 (mod 3) 和 x ≡ 3 (mod 5) 這樣的方程 — 其中模數是各個模的乘積（或最小公倍數）。這個方法大約距今 1500 年前來自中國古代數學文獻《孫子算經》，而今天它被廣泛應用於 RSA 密碼學最佳化、日曆計算和糾錯碼，同時也是離散數學和數論課程的主要內容。本指南將詳細介紹計算器的工作原理、如何檢查系統是否有解、如何求解該方法依賴的模逆元、兩個完整的工作示例（一個帶互質模數，一個不帶）以及常見錯誤和練習題。
目錄
什麼是中文剩餘定理？
中文剩餘定理（CRT）說如果您有一個同餘方程組 x ≡ a₁ (mod m₁)、x ≡ a₂ (mod m₂)、...、x ≡ aₙ (mod mₙ)，且模數 m₁、m₂、...、mₙ 兩兩互質（每對除了 1 以外沒有公因子），那麼對於 x 模 M 恰好存在一個解，其中 M = m₁ × m₂ × ... × mₙ。該定理因其最早在 3 至 5 世紀的中國文獻《孫子算經》（孫子的算術手冊）中出現而得名，文獻中提出了現在經典的謎題：找一個數，用 3 除餘 2，用 5 除餘 3，用 7 除餘 2。這個謎題和求解它的 CRT 方法在課堂外不斷出現：RSA 密碼學使用 CRT 透過處理較小的模而不是一個巨大的模來加快解密速度，電腦科學家使用它將大數表示為較小餘數的元組以進行更快的算術運算，日曆系統使用它來協調不同長度的週期（一週的天數、一個月的天數和閏年週期）。
中文剩餘定理：對於兩兩互質的模數 m₁、...、mₙ，系統 x ≡ aᵢ (mod mᵢ) 對於 M = m₁ × m₂ × ... × mₙ 恰好有一個解。
中文剩餘定理計算器如何工作？
中文剩餘定理計算器自動執行四個階段，這些階段在一個系統有三個或更多同餘方程時手工追蹤會很繁瑣，特別是模逆元計算。在內部，它將每個同餘方程視為一對 (aᵢ, mᵢ)，確認模數可以一起使用，然後使用加權和而不是試錯法構建唯一解。理解這四個階段是讓您能夠驗證計算器輸出或在不允許使用計算器的考試中手工解決相同問題的關鍵。
1. 第 1 步：檢查模數
確認每對模數都互質（gcd = 1）。如果任何一對共享公因子，計算器將切換到下一部分描述的兼容性檢查，而不是使用標準公式。
2. 第 2 步：計算組合模數 M
將所有模數相乘：M = m₁ × m₂ × ... × mₙ。這是最終組合答案的模數。
3. 第 3 步：找到每個部分乘積及其模逆元
對於每個同餘方程 i，計算 Mᵢ = M / mᵢ（除了 mᵢ 以外所有模數的乘積），然後找到 Mᵢ 模 mᵢ 的模逆元 — 稱為 yᵢ，其中 Mᵢ × yᵢ ≡ 1 (mod mᵢ)。
4. 第 4 步：組合和約化
對每個同餘方程求 aᵢ × Mᵢ × yᵢ 的和，然後將該和對 M 求模以獲得唯一的最小非負解 x。
每個中文剩餘定理計算器背後的公式：x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M，其中 Mᵢ = M/mᵢ，yᵢ 是 Mᵢ 模 mᵢ 的模逆元。
如何檢查模數是否兼容？
中文剩餘定理的教科書版本需要兩兩互質的模數，但真實系統 — 特別是出現在調度或密碼學問題中的系統 — 通常有共享因子的模數。CRT 的廣義版本仍然適用，但僅當系統首先通過兼容性檢查時才適用：對於每對同餘方程 x ≡ aᵢ (mod mᵢ) 和 x ≡ aⱼ (mod mⱼ)，兩者必須在重疊部分上一致，意味著 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))。如果這個檢查對任何一對失敗，系統無論如何都沒有解 — 一個好的計算器會報告這一點，而不是返回一個錯誤的數字。
1. 第 1 步：計算每對模數的 gcd(mᵢ, mⱼ)
對於兩個同餘方程的系統，只有一對要檢查。對於三個同餘方程的系統，檢查所有三對。
2. 第 2 步：將兩個餘數都對該 gcd 求模
取 aᵢ mod gcd(mᵢ, mⱼ) 和 aⱼ mod gcd(mᵢ, mⱼ)。如果它們匹配，則該對兼容。
3. 第 3 步：不兼容系統的示例
取 x ≡ 1 (mod 4) 和 x ≡ 0 (mod 6)。gcd(4, 6) = 2。約化：1 mod 2 = 1，0 mod 2 = 0。由於 1 ≠ 0，沒有整數同時滿足兩個同餘方程 — 系統沒有解，中文剩餘定理計算器應該明確標記這一點，而不是強行給出一個答案。
非互質模數的兼容性規則：x ≡ aᵢ (mod mᵢ) 和 x ≡ aⱼ (mod mⱼ) 只有當 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)) 時才能都成立。
什麼是模逆元以及如何找到它？
數字 a 模 m 的模逆元是另一個數字 b，使得 a × b ≡ 1 (mod m) — 它在固定模數內的整數範圍內發揮與普通除法中 1/a 相同的作用。模逆元存在當且僅當 gcd(a, m) = 1，這正是標準中文剩餘定理要求兩兩互質模數的原因：它保證每個 Mᵢ 在模 mᵢ 下都有逆元。手工找到模逆元最可靠的方法是擴展歐幾里得演算法，它向前執行普通 gcd 演算法，然後向後工作以將 1 表示為 a 和 m 的組合。
1. 第 1 步：向前執行歐幾里得演算法
找到 4 模 7 的逆元。重複除法：7 = 1×4 + 3，然後 4 = 1×3 + 1，然後 3 = 3×1 + 0。餘數是 3、然後 1、然後 0，確認 gcd(4, 7) = 1，所以逆元存在。
2. 第 2 步：向後工作以隔離 1
從倒數第二行，1 = 4 − 1×3。代入第一行的 3 = 7 − 1×4：1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7。
3. 第 3 步：讀出逆元
方程 1 = 2×4 − 1×7 意味著 2×4 ≡ 1 (mod 7)，所以 4 模 7 的逆元是 2。快速檢查：4 × 2 = 8 = 7 + 1，確實 ≡ 1 (mod 7)。
對於小模數，通常更快的做法是直接測試候選：將 a 乘以 1、2、3、... 模 m，直到乘積為 1。對於較大的模數，擴展歐幾里得演算法更為可靠。
工作示例：求解互質模數的同餘方程
這是經典的孫子算經問題：找 x 使得 x ≡ 2 (mod 3)、x ≡ 3 (mod 5) 和 x ≡ 2 (mod 7)。模數 3、5 和 7 兩兩互質，所以標準 CRT 公式可以直接應用。
1. 第 1 步：計算 M
M = 3 × 5 × 7 = 105。
2. 第 2 步：計算每個 Mᵢ 及其逆元
M₁ = 105/3 = 35。35 mod 3 = 2，2 模 3 的逆元是 2（因為 2×2 = 4 ≡ 1 mod 3）。 M₂ = 105/5 = 21。21 mod 5 = 1，1 模 5 的逆元是 1。 M₃ = 105/7 = 15。15 mod 7 = 1，1 模 7 的逆元是 1。
3. 第 3 步：組合
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23。
4. 第 4 步：驗證
23 ÷ 3 = 7 餘 2 ✓。23 ÷ 5 = 4 餘 3 ✓。23 ÷ 7 = 3 餘 2 ✓。最小非負解是 x = 23，每個其他解是 23 + 105k（對於任意整數 k）。
x ≡ 23 (mod 105) — 中文剩餘定理計算器立即返回的答案，也是一千多年前開啟數論這個分支的同一個謎題。
工作示例：協調非互質模數
現在求解 x ≡ 3 (mod 4) 和 x ≡ 1 (mod 6)，其中 4 和 6 不互質（它們共享因子 2）。互質模數示例中的標準公式不能直接應用，但系統仍可能有一個唯一解（模數的最小公倍數），前提是它首先通過兼容性檢查。
1. 第 1 步：檢查兼容性
gcd(4, 6) = 2。約化兩個餘數：3 mod 2 = 1，1 mod 2 = 1。它們匹配，所以系統兼容且解存在。
2. 第 2 步：找到組合模數
不是將 4 × 6 = 24 相乘，而是使用最小公倍數：lcm(4, 6) = 12。解將模 12 唯一，不是模 24。
3. 第 3 步：代入和求解
從第一個同餘方程寫出 x = 4k + 3，然後代入第二個：4k + 3 ≡ 1 (mod 6)，所以 4k ≡ −2 ≡ 4 (mod 6)。兩邊和模數都共享因子 gcd(4, 6) = 2，所以將整個同餘方程除以 2：2k ≡ 2 (mod 3)。2 模 3 的逆元是 2，所以 k ≡ 2×2 ≡ 1 (mod 3)。
4. 第 4 步：重構 x
對於任意整數 j，k = 3j + 1，所以 x = 4(3j + 1) + 3 = 12j + 7。最小非負解是 x = 7。
5. 第 5 步：驗證
7 mod 4 = 3 ✓。7 mod 6 = 1 ✓。所以 x ≡ 7 (mod 12) 是正確的，將同餘方程除以共享因子 — 而不是忽略它 — 是使非互質 CRT 工作的步驟。
當模數共享公因子時，不能按原樣使用互質公式 — 在找逆元前，必須將結果同餘方程除以 gcd(mᵢ, mⱼ)，否則逆元不存在。
重構最小非負解
每個通過兼容性檢查的中文剩餘定理系統有無窮多個整數解，不僅僅是一個 — 但它們都模 M（或在非互質情況下模 lcm(m₁, ..., mₙ)）相同餘。按慣例，計算器報告該無窮族的最小非負代表，滿足 0 ≤ x₀ < M 的值 x₀，因為它是最容易表述、比較和驗證的單一規範答案。每個其他解只是 x₀ 加上或減去 M 的倍數。
1. 約化負中間和
計算器方法第 4 步中的加權和如果任何餘數 aᵢ 為負或如果模逆元被計算為負代表則可能為負。如果和為 S = −37，M = 45，重複加 M 直到結果非負：−37 + 45 = 8，所以最小非負解是 x₀ = 8，不是 −37。
2. 完整的解集
一旦您有了 x₀，完整的解集是形式為 x₀ + kM（對於 k = ...、−2、−1、0、1、2、...）的每個整數。在上面的孫子示例中，那是 23、128、233、...，也包括 −82、−187 等 — 但除非要求特定範圍，23 是您報告的解。
一個負數或超大的中間結果並不錯誤 — 它只是還沒有被約化。加上或減去 M 的倍數，直到值落在 [0, M)。
最常見的中文剩餘定理錯誤是什麼？
CRT 問題中的大多數錯誤來自跳過檢查而不是有缺陷的最終計算，這就是為什麼在問題開始時放慢速度而不是在結束時是值得的。
1. 將互質公式應用於非互質模數
如果任何兩個模數共享因子，將 M 計算為它們的直接乘積並以標準方式查找模逆元將失敗或產生錯誤答案 — 始終首先檢查每對的 gcd(mᵢ, mⱼ) = 1。
2. 將模逆元與常規倒數混淆
4 模 7 的逆元是 2，不是 1/4 — 模逆元是透過擴展歐幾里得演算法（或小模數的試乘）找到的整數，從不是分數。
3. 未能正確約化負數模 m
−2 mod 6 是 4，不是 −2 也不是 2 — 持續加模數直到結果在範圍 [0, m) 內。截斷或取絕對值而不是加模數是錯誤答案的常見來源。
4. 忘記在非互質系統中除以共享因子
當模數共享公因子時，像 4k ≡ 4 (mod 6) 這樣的同餘方程必須透過 gcd(4, 6) = 2 除以變成 2k ≡ 2 (mod 3)，然後才能找到逆元 — 4 在模 6 下根本沒有逆元，因為 gcd(4, 6) ≠ 1。
5. 在約化最終和模 M 之前停止
第 4 步中的加權和（例如，孫子問題中的 233）不是最終答案 — 它必須對 M 求模（233 mod 105 = 23）以達到最小非負解。
如果您的答案在代入時不滿足每個原始同餘方程，首先重新檢查兼容性測試和模逆元 — 那是幾乎每個 CRT 錯誤實際發生的地方。
練習題：測試您的中文剩餘定理計算器技能
在將答案與下面的解決方案進行比較前，手工解決這三個系統，首先檢查兩兩互質性或兼容性。第二個問題故意無法解決 — 識別這一點與找到存在解的數值答案一樣重要。
1. 問題 1（互質）
求解：x ≡ 1 (mod 3)、x ≡ 4 (mod 5)、x ≡ 6 (mod 7)。答案：M = 105。M₁ = 35，在模 3 下的逆元是 2；M₂ = 21，在模 5 下的逆元是 1；M₃ = 15，在模 7 下的逆元是 1。和 = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244。244 mod 105 = 34。檢查：34 mod 3 = 1 ✓、34 mod 5 = 4 ✓、34 mod 7 = 6 ✓。解：x ≡ 34 (mod 105)。
2. 問題 2（不兼容的模數 — 無解）
求解：x ≡ 2 (mod 8)、x ≡ 5 (mod 12)。gcd(8, 12) = 4。約化：2 mod 4 = 2，5 mod 4 = 1。由於 2 ≠ 1，系統不兼容且無解 — 中文剩餘定理計算器應該返回這個結論而不是一個錯誤的數字。
3. 問題 3（兼容的非互質模數）
求解：x ≡ 5 (mod 9)、x ≡ 2 (mod 6)。gcd(9, 6) = 3。約化：5 mod 3 = 2，2 mod 3 = 2 — 兼容。lcm(9, 6) = 18。寫出 x = 9k + 5，代入：9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6)。除以 gcd(9, 6) = 3：3k ≡ 1 (mod 2) → k ≡ 1 (mod 2)。所以 k = 2j + 1，給出 x = 9(2j+1) + 5 = 18j + 14。檢查：14 mod 9 = 5 ✓、14 mod 6 = 2 ✓。解：x ≡ 14 (mod 18)。如果您想在像這樣的問題上仔細檢查每個模逆元和約化步驟，Solvify 的分步數學求解器將以本指南相同的方式逐步講解每個階段。
快速建立中文剩餘定理真正流暢性的最快方法是求解互質、非互質但兼容以及不兼容系統的組合 — 識別您處於哪種情況是該技能的一半。
相關文章
相關數學解題工具
智能掃描求解器
拍攝同餘方程組或數論問題的照片，立即獲得逐步中文剩餘定理解決方案。
逐步解決方案
看到每個模逆元、兼容性檢查和約化步驟都有解釋，而不僅僅是最終餘數。
AI 數學導師
提出關於模逆元、互質模數或為什麼系統無解的後續問題，答案針對您的確切問題量身定製。