什么是中国剩余定理？
中国剩余定理（CRT）是数论中的经典结论，最早可追溯至中国古代算书《孙子算经》中"物不知数"问题。它指出：若有一组同余式 \(x \equiv a_1 \pmod{m_1}\)、\(x \equiv a_2 \pmod{m_2}\)、……，且这些模数两两互质（彼此之间没有公因数），那么在模 \(M = m_1 \cdot m_2 \cdot \ldots\) 的意义下，存在唯一的解 \(x\)。本计算器会帮你求出其中最小的非负解。
如何使用本计算器
分别输入每个余数 \(a_i\) 及其对应的模数 \(m_i\)。你可以求解两个或三个同余式组成的方程组——如果只需要两个，把第三个模数留空即可。工具会先检验各模数是否两两互质，再返回 \(x\) 和合并后的模数 \(M\)。凡是形如 \(x + Mk\)（\(k\) 为任意整数）的数值，同样都是该方程组的解。
公式详解
令 \(M = \prod m_i\)。对每个同余式，定义 \(M_i = M / m_i\)，以及 \(y_i = M_i^{-1} \bmod m_i\)（即用扩展欧几里得算法求出的模逆元）。则解为加权求和 $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$ 由于 \(M_i\) 能被除 \(m_i\) 以外的所有模数整除，因此每一项都只会对它自己对应的那个同余式贡献正确的余数。
实例演算
求解 \(x \equiv 2 \pmod 3\) 与 \(x \equiv 1 \pmod 4\)。这里 \(M = 3 \cdot 4 = 12\)。\(M_1 = 4\)，而 \(4 \equiv 1 \pmod 3\)，所以 \(y_1 = 1\)；\(M_2 = 3\)，而 \(3 \equiv 3 \pmod 4\)，所以 \(y_2 = 3\)（因为 \(3 \cdot 3 = 9 \equiv 1\)）。于是 $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 验证：\(5 \bmod 3 = 2\) ✓，\(5 \bmod 4 = 1\) ✓。
常见问题
为什么模数必须互质？如果两个模数有公因数，方程组在它们的最小公倍数意义下可能无解，也可能有多个解，此时标准的中国剩余定理公式便不再适用。
"最小非负解"是什么意思？所有解彼此都相差 \(M\) 的整数倍；计算器返回的是落在 \(0\) 到 \(M-1\) 范围内的那一个。
余数可以是负数吗？可以。在求解之前，它们会先按各自的 \(m_i\) 取模，化归到 \(0\) 到 \(m_i-1\) 的范围内。
