中國剩餘定理（CRT）計算器 — 求解一次同餘方程組
使用中國剩餘定理求解形如 x ≡ a₁ (mod n₁)、x ≡ a₂ (mod n₂)… 的同餘方程組。自動驗證各模數是否兩兩互素，並給出最小非負整數解與通解。
計算示例：《孫子算經》中的「物不知數」問題
這是中國剩餘定理起源之一的經典問題，出自約西元3至5世紀的算術著作《孫子算經》。「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」的答案是：以105為模，餘數為23。
| 條件1 | x ≡ 2 (mod 3) |
|---|---|
| 條件2 | x ≡ 3 (mod 5) |
| 條件3 | x ≡ 2 (mod 7) |
| 解 | x ≡ 23 (mod 105) |
什麼是中國剩餘定理（CRT）
中國剩餘定理是用以求解**「三除餘二、五除餘三、七除餘二之數為何」**這般聯立同餘式的定理。諸模若兩兩互質，則於諸模之積為模的範圍內，其解唯一而定。本工具可填入最多5條同餘式，求出最小的非負整數解與通解。
**本工具僅處理諸模皆兩兩互質的「古典」形式。**若任二模有大於1的公因數便無從求解，屆時將顯示相應錯誤（諸模不互質時的廣義中國剩餘定理不在本工具範圍內）。**模須為2以上的整數**，餘數則自動正規化至0以上、小於該模，故縱填入不小於模之值或負值亦可。內部採多倍長整數運算，故無位數之限。
中國剩餘定理計算器的使用方式
- 填入餘數與模 每條同餘式各填餘數 a 與模 n，對應 x ≡ a (mod n) 之形式。
- 增添同餘式 以「新增同餘式」最多可排列5條。條數既增，解之唯一性所及的範圍（諸模之積）亦隨之擴大。
- 求解 按下「求解」，即得最小的非負整數解，以及以諸模之積為模的通解。
- 追蹤計算過程 將就各同餘式列出 Nᵢ（諸模之積除去自身之模者）與 Mᵢ（Nᵢ 之逆元），可用以核對手算之答案。
- 不互質則無從求解 若顯示「諸模不互質」，即表示混有如4與6這般具公因數之模。請重新檢視組合。
用好本工具的小技巧
- 如果模數（nᵢ）之間不是兩兩互素，將會報錯。例如 mod 4 與 mod 6 的最大公約數為2，本計算器無法求解（這需要用到廣義中國剩餘定理）。
- 即使餘數 aᵢ 大於等於模數 nᵢ 或為負數也沒關係，程式內部會自動將其歸約到 mod nᵢ 後再計算。
- 最多可以新增5個同餘式（最少需要2個）。這類計算也可用於「猜測士兵人數」等需要同時滿足多個週期條件的經典謎題。
- 結果中的通解以 x ≡ 解 (mod N) 的形式給出：在解上加上 N 的任意整數倍，仍然滿足所有原始條件。
中國剩餘定理派上用場的情境
數論習題與考試準備
可用以核對手解之答案。因兼列 Nᵢ・Mᵢ 之中間值，故能縮小出錯之處。
學習密碼演算法時
用以加速RSA解密的CRT最佳化，即直接運用此定理。可循數值追蹤其機理。
求週期之重合時
以不同週期反覆之事象同時發生的時刻，可表為聯立同餘式。
重現古典問題時
《孫子算經》之「物不知其數」（三除餘二、五除餘三、七除餘二之數），以105為模即為23。可照數填入驗之。
欲使用相關數論工具時
逆元與同餘式本身可看同餘式・模運算；最大公因數可看最大公因數・最小公倍數；質因數分解可看質因數分解。
與中國剩餘定理相關的用語
- 中國剩餘定理（CRT）
- 指陳述「諸模互質之聯立同餘式，以諸模之積為模存在唯一解」的定理。
- 同餘式
- 指 x ≡ a (mod n) 之形式，表示「x 除以 n 之餘數等於 a」。
- 模（modulus）
- 即除數。本工具限於2以上之整數。
- 互質
- 指兩整數之最大公因數為1。古典CRT要求任取二模皆須互質。
- 兩兩互質
- 指三數以上者，任取其二皆互質。縱整體之最大公因數為1，亦有非兩兩互質之情形。
- 模逆元
- 指滿足 a·x ≡ 1 (mod n) 之 x。於CRT中，用於求 Nᵢ 之逆元 Mᵢ。
- 擴展歐幾里得演算法
- 指同時求最大公因數與貝祖係數之演算法，用於計算模逆元。
- 通解
- 指於最小非負整數解上加諸模之積的整數倍所得之全體，以 x ≡ 23 (mod 105) 之形表示。
常見問題
閒話 ― 從三世紀的算術典籍到RSA加密的提速
中國剩餘定理的思想最早可追溯至《孫子算經》——一部約成書於西元3至5世紀的中國算術典籍——中著名的「物不知數」問題：「三三數之剩二，五五數之剩三，七七數之剩二」。這個古老的謎題已經體現出與現代中國剩餘定理本質相同的思路：由若干個除法餘數反推出原始的未知數。
中國剩餘定理在現代最實用的應用之一，是加速RSA加密演算法的解密過程。RSA解密需要對一個大數取冪後再對合數 n = p × q（p、q 均為大素數）取模。相比直接對 n 取模，利用中國剩餘定理分別對 p 和 q 獨立計算再合併結果，理論上可將解密速度提升至接近4倍——這項技術被稱為「CRT-RSA」，已被許多密碼學庫採用。
本工具支援的是要求所有模數兩兩互素的「經典」中國剩餘定理。當模數存在公因數時（例如 mod 4 與 mod 6），有時仍然存在解，但判定與計算需要用到更為複雜的廣義中國剩餘定理演算法，這超出了本工具的範圍。