中国剩余定理

目录

• 写在前面
• 正文
  • 中国剩余定理公式：
  • 中国剩余定理拓展：
  • 大数翻倍法

写在前面

Q：中国剩余定理很难吗？

A：就是个求解同余方程组的东东

(话说 \(OI\) 只要能理解应用就好吧，证明是不是可以先放一放)因为我太菜了

Update 2021/04/11：终于理解中国剩余定理，还是tcl

---

正文

《孙子算经》中有这么一道题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

翻译一下就是：已知一个正整数模3余2，模5余3，模7余2，求这个数是几？

写成数学语言，就是求解同余方程组

\[\begin{aligned} & x \equiv 2 \pmod 3 \\ & x \equiv 3 \pmod 5 \\ & x \equiv 5 \pmod 7 \\ \end{aligned} \]

乍一看，这不很简单蛮，随便带近两个数试试不就行了

但是你现在可以直接观察并且数据小，如果数据大了呢，同余方程组不只是三个呢？

这就需要我们的“中国剩余定理”登场了

中国剩余定理公式：

设正整数 \(m_1, m_2, m_3, ···,m_k\) 两两互素，则同余方程组

\[\begin{aligned} & x \equiv a_1 \pmod {m_1} \\ & x \equiv a_2 \pmod {m_2} \\ & x \equiv a_3 \pmod {m_3} \\ & ··· \\ & x \equiv a_k \pmod {m_k} \end{aligned} \]

有整数解。并且在模 \(M = m_1 \times m_2 \times ··· \times m_k\) 下解是唯一的，解为

\[x \equiv (a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ··· + a_k M_k M_k^{-1}) mod \ \ M \]

其中 \(M_i = M / m_i\) ， 而 \(M_i^{-1}\) 为 \(M_i\) 模 \(m_i\) 的逆元

中国剩余定理拓展：

（求解模数不互质情况下的同余方程组）

普通中国剩余定理要求所有的 \(m_i\) 互素，那么如果不互素呢？怎么求解同余方程组？

这种情况可以考虑两两合并，假设合并如下两个方程：

\[x = a_1 + m_1 x_1 \]

\[x = a_2 + m_2 x_2 \]

那么得到：

\[a_1 + m_1 x_1 = a_2 + m_2 x_2 \Rightarrow m_1 x_1 + m_2 x_2 = a_2 - a_1\]

我们需要求出一个最小的 \(x\) 使它满足：

\[x = a_1 + m_1 x_1 = a_2 + m_2 x_2 \]

那么 \(x_1\) 和 \(x_2\) 的值要仅可能的小，于是我们又扩展欧几里得算法求出 \(x_1\) 的最小整数解，将它代回 \(a_1 + m_1 x_1\) ，得到 \(x\) 的一个特解 \(x^{,}\) ，当然也是最小整数解。

所以 \(x\) 的通解一定是 \(x^{,}\) 加上 \(lcm(m_1,m_2) \times k\) 这样才能保证 \(x\) 模 \(m_1\) 和 \(m_2\) 的余数是 \(a_1\) 和 \(a_2\) 。由此，我们把这个 \(x^{,}\) 当做新的方程的余数，把 \(lcm(m_1,m_2) \times k\) 当做新的方程的模数。（这一段是关键）

合并完成：

\[x \equiv x^{,} \pmod {lcm(m_1,m_2)} \]

大数翻倍法

复杂度有保证，码量短小精湛！

详见这篇

---

想学中国剩余定理很久了，第一次听说是在夏令营的时候，看到同宿舍某大佬的课程表上有这个名词，感觉挺高大上的，前几天忙着期中考咕咕咕了，如今终于有机会更一篇关于它的笔记了，开心>-