为什么迭代中国剩余定理方法中的步长会更新为已合并模数的最小公倍数？

适用条件

• 一个数字目前满足一组同余方程。
• 新的步长必须保留所有这些同余方程的余数。

理解与推导

1. 识别当前满足的同余方程的模数。
2. 计算这些模数的最小公倍数（LCM）。
3. 将 LCM 加到当前解上以生成下一个候选数。
4. 观察到因为 LCM 能被每个模数整除，所以每个模数的余数保持不变。

例子

在视频中，在找到 11 满足 x ≡ 3 (mod 4) 和 x ≡ 5 (mod 6) 后，演讲者说：“你可以将它增加一个能被到目前为止所有模数（4 和 6）整除的数。它们的最小公倍数 LCM 是 12，如果你给某个数加上 12，你不会改变模 6 和模 4 的余数，因为 12 能被 6 和 4 整除。”

容易误解的地方

• 认为加到解上的任何数字都会保留余数。
• 假设步长应该是模数的乘积，如果模数不互质，这可能会跳过有效的解。

观看对应讲解

继续追问

• 当 a 和 b 不互质时，LCM(a,b) 的公式是什么？
• 中国剩余定理中的等余数捷径是如何工作的？
• 为什么允许重新排列同余方程？