中国剩余定理（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），有时仍然存在解，但判定与计算需要用到更为复杂的广义中国剩余定理算法，这超出了本工具的范围。