中国剩余定理计算器

中国剩余定理通常缩写为 CRT，可将多个模运算条件合并为一个解。例如 x ≡ 2（模 3）表示 x 除以 3 的余数为 2。本计算器接收三个这样的方程，找出同时满足所有方程的最小非负整数。 经典定理要求模数两两互质，即任意一对模数的最大公约数都是一。在此条件下，以所有模数的乘积为模，恰有一个解。模数为 3、5、7 时，乘积为 105。若最小解为 23，则 23、128、233，以及通过加减 105 得到的所有整数，都满足同一方程组。 构造算法先将所有模数相乘，得到 M。对于每个方程，将 M 除以该方程的模数，得到部分乘积。由于模数两两互质，该部分乘积在被除去的模数下存在乘法逆元。将每个余数、部分乘积和逆元相乘，可构造出满足一个同余条件、在其他模数下余数为零的项。把这些项相加，再对 M 取模，即得到答案。 CRT 的用途远不止教科书中的数论。它可用于高效大整数运算、密码学实现、编码理论、日历周期、轮班安排、计算机代数和由余数重建数值。当复杂运算可以拆分为多个模数下较小且独立的运算，再合并结果时，这一定理尤其有用。 请输入整数余数和大于一的模数。余数可以为负，也可以大于模数，因为取模运算会自动将其规范化。本版本明确要求模数两两互质，以符合经典定理并保证唯一剩余类。不互质的模数有时也能组成可解方程组，但需要额外的相容性检查，不在本计算器的处理范围内。请将结果分别除以每个模数，检查所得余数，以验证答案。