余数序列技巧如何在求解中国剩余定理中的同余方程时避免计算大数？

适用条件

• 你有一个满足先前同余方程的候选等差数列。
• 你需要找到满足新同余方程 x ≡ r (mod m) 的第一项。

理解与推导

1. 将当前起始解对新目标模数 m 取模。
2. 将当前步长对新目标模数 m 取模。
3. 通过反复加上步长的余数（模 m）来生成余数序列。
4. 计算需要多少次加法才能达到目标余数 r。
5. 将步长乘以这个计数，并加到起始解上，得到新的特解。

例子

为了用起始解 21 和步长 60 满足 x ≡ 3 (mod 7)，视频计算 21 mod $7 = 0$ 和 60 mod $7 = 4$。它生成余数序列 0, 4, 1, 5, 2, 6, 3。达到 3 需要 6 步，所以解是 $21 + 6*60 = 381$。

容易误解的地方

• 计算等差数列中的实际大数（例如 21, 81, 141...）并手动检查它们的余数。
• 忘记在余数序列的每一步取模。

观看对应讲解

继续追问

• 为什么余数序列会形成一个循环？
• 使用此技巧找到解最多需要多少步？
• 找到特解后如何求通解周期？