浅谈中国剩余定理

中国剩余定理

定义

中国剩余定理（CRT）可以求解如下形式的一元线性同余方程组（其中 \(n_{1},n_{2},\dots,n_{k}\) 两两互质）

\[\left\{\begin{matrix} x\equiv a_{1}\pmod{n_{1}}\\ x\equiv a_{2}\pmod{n_{2}}\\ \vdots\\ x\equiv a_{k}\pmod{n_{k}} \end{matrix}\right. \]

过程

• 计算所有模数的积 \(n\)

• 对于第 \(i\) 个方程：

  • 计算 \(m_{i}=\frac{n}{n_{i}}\);

  • 计算 \(m_{i}\) 在模 \(n_{i}\) 意义下的逆元 \(m_{i}^{-1}\)

  • 计算 \(c_{i}=m_{i}m_{i}^{-1}\) （不要对 \(n_{i}\) 取模）

• 方程组在模 \(n\) 意义下的唯一解为 \(x=\sum_{i=1}^{k}a_{i}c_{i}\pmod{n}\)

证明

我们需要证明上面算法计算所得的 \(x\) 对于任意 \(i=1,2,\dots,k\) 满足 \(x\equiv a_{i}\pmod{n_{i}}\)

当 \(i\ne j\) 时，有 \(m_{j}\equiv 0\pmod{n_{i}}\) ，故 \(c_{j}\equiv m_{j}\equiv 0\pmod{n_{i}}\) 又有 \(c_{i}\equiv m_{i}\times (m_{i}^{-1}\bmod{n_{i}})\equiv 1\pmod{n_{i}}\)，所以我们有：

\[x\equiv \sum_{j=1}^{k}a_{j}c_{j} \pmod{n_{i}}\\ \equiv a_{i}c_{i}\pmod{n_{i}}\\ \equiv a_{i}\times m_{i}\times(m_{i}^{-1}\bmod{n_{i}})\pmod{n_{i}}\\ \equiv a_{i}\pmod{n_{i}} \]

其中 \(m_{i}^{-1}\) 表示 \(m_{i}\) 的逆元。

即对于任意 \(i=1,2,\ldots,k\)，上面算法提到的 \(x\) 总是满足 \(x\equiv a_{i}\pmod{n_{i}}\)，即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 \(a_{i}\) 作特殊限制，所以任何一组输入都对应一个解 \(x\)

另外，若 \(x\ne y\)，则总存在 \(i\) 使得 \(x\) 和 \(y\) 在模 \(n_{i}\) 下不同余

故系数列表 \(\{a_{i}\}\) 与解 \(x\) 之间是一一映射关系，方程组总是有唯一解

P1495【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷

参考代码：

Garner 算法

CRT的另一个用途是用一组比较小的质数来表示一个大的整数。

例如，若 \(a\) 满足如下线性方程组，且 \(a<\prod_{i=1}^{k}P_{i}\) （其中 \(P_{i}\) 为质数）：

\[\left\{\begin{matrix} a\equiv a_{1}\pmod{p_{1}}\\ a\equiv a_{2}\pmod{p_{2}}\\ \vdots\\ a\equiv a_{k}\pmod{p_{k}} \end{matrix}\right. \]

我们可以用以下形式的式子（称作 \(a\) 的混合基数表示）表示 \(a\)：

\[a=x_{1}+x_{2}p_{1}+x_{3}p_{1}p_{2}+\dots+x_{k}p_{1}\dots p_{k-1} \]

Garner 算法将用来计算系数 \(x_{1},\dots,x_{k}\)。

令 \(r_{ij}\) 为 \(p_{i}\) 在模 \(p_{j}\) 意义下的逆：

\[p_{i}\times r_{ij}\equiv 1\pmod{p_{j}} \]

把 \(a\) 带入我们得到的第一个方程：

\[a_{1}\equiv x_{1}\pmod{p_{1}} \]

代入第二个方程得到：

\[a_{2}\equiv x_{1}+x_{2}p_{1}\pmod{p_{2}} \]

方程两边减 \(x_{1}\)，除 \(p_{1}\) 后得

\[a_{2}-x_{1}\equiv x_{2}p_{1}\pmod{p_{2}}\\ (a_{2}-x_{1})r_{1,2}\equiv x_{2}\pmod{p_{2}}\\ x_{2}\equiv (a_{2}-x_{1})r_{1,2}\pmod{p_{2}} \]

类似地，我们可以得到：

扩展CRT

上面的朴素 CRT 是求解

\[\left\{\begin{matrix} x\equiv a_{1}\pmod{n_{1}}\\ x\equiv a_{2}\pmod{n_{2}}\\ \vdots\\ x\equiv a_{k}\pmod{n_{k}} \end{matrix}\right. \]

一类的同余方程组，但是如果 \(n_{1},n_{2},\dots,n_{k}\) 不互质的话怎么办？

据某位学长说扩展中国剩余定理跟中国剩余定理没半毛钱关系，一个是用扩展欧几里得，一个是用构造

首先我们从简单入手，考虑只有两个式子的情况

\[x\equiv a_{1}\pmod{n_{1}}\\ x\equiv a_{2}\pmod{n_{2}} \]

将两个式子变形：

\[x=a_{1}+n_{1}k_{1}\\ x=a_{2}+n_{2}k_{2} \]

联立：

\[a_{1}+n_{1}k_{1}=a_{2}+n_{2}k_{2} \]

移项：

\[n_{1}k_{1}=a_{2}-a_{1}+n_{2}k_{2} \]

在这里需要注意就是这个方程有解的条件是 \(\gcd(n_{1},n_{2})\mid(a_{2}-a_{1})\)，因为后面会用到 \(\frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}\) 这一项，如果不能整除会出现小数。

对于上面的方程，两边同除 \(\gcd(n_{1},n_{2})\)

\[\frac{n_{1}k_{1}}{\gcd(n_{1},n_{2})}= \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}+ \frac{n_{2}k_{2}}{\gcd(n_{1},n_{2})}\\ \frac{n_{1}}{\gcd(n_{1},n_{2})}k_{1}= \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}+ \frac{n_{2}}{\gcd(n_{1},n_{2})}k_{2}\\ \]

转换一下：

\[\frac{n_{1}}{\gcd(n_{1},n_{2})}k_{1}\equiv \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}\pmod{ \frac{n_{2}}{\gcd(n_{1},n_{2})}} \]

此时我们把 \(k_{2}\) 搞没了

同余式两边同除 \(\frac{n_{1}}{\gcd(n_{1},n_{2})}\)

\[k_{1}\equiv inv(\frac{n_{1}}{\gcd(n_{1},n_{2})},\frac{n_{2}}{\gcd(n_{1},n_{2})})\times \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}\pmod{\frac{n_{2}}{\gcd(n_{1},n_{2})}} \]

\(inv(a,b)\) 表示 \(a\) 在模 \(b\) 意义下的逆元。

\[k_{1}\equiv inv(\frac{n_{1}}{\gcd(n_{1},n_{2})},\frac{n_{2}}{\gcd(n_{1},n_{2})})\times \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}+\frac{n_{2}}{\gcd(n_{1},n_{2})}\times y \]

我们把开头的式子拿过来，把 \(k_{1}\) 代回去。

\[x=inv(\frac{n_{1}}{\gcd(n_{1},n_{2})},\frac{n_{2}}{\gcd(n_{1},n_{2})})\times \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}\times n_{1}+y\frac{n_{1}n_{2}}{\gcd(n_{1},n_{2})} +a_{1} \]

\[x\equiv inv(\frac{n_{1}}{\gcd(n_{1},n_{2})},\frac{n_{2}}{\gcd(n_{1},n_{2})})\times \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})}\times n_{1}+a_{1}\pmod{\frac{n_{1}n_{2}}{\gcd(n_{1},n_{2})}} \]

此时，整个式子中的元素我们都知道了

这个式子可以看作是

\[x\equiv a\pmod{n} \]

其中：

\[a=(inv(\frac{n_{1}}{\gcd(n_{1},n_{2})},\frac{n_{2}}{\gcd(n_{1},n_{2})}) \times \frac{a_{2}-a_{1}}{\gcd(n_{1},n_{2})})\%\frac{n_{2}}{\gcd(n_{1},n_{2})} \times n_{1}+a_{1} \]

\[n=\frac{n_{1}n_{2}}{\gcd(n_{1},n_{2})} \]

如果是多个式子可以逐个合并。

上面的式子如果你觉得又臭又长可以把 \(inv\) 及括号里的替换为用扩欧对两模数求逆元的 \(x\)，他俩是一个数；\(n\) 也就是 \(\text{lcm}(n_{1},n_{2})\)。

P4777【模板】扩展中国剩余定理（EXCRT） - 洛谷

部分参考自 OI Wiki