具体数学独立剩余旁注

注：本节内容为《具体数学》(原书第二版) 第四章数论 4.7 独立剩余的旁注。

P106 独立剩余到底在做什么？

独立剩余可以将两个数对于一个大模数的 模数加法，模数减法，模数乘法，转换为这两个数对于若干个小模数的 模数加法，模数减法，模数乘法。

P106 独立剩余怎么做？

首先，我们定义 剩余系 (Residue Number System)

$$
\operatorname{Res}(x) = (x \bmod m_1, \cdots ,x \bmod m_r), 1 \leq j < k \leq r \Rightarrow m_j \perp m_k
$$

其中

$$
\prod _ k m_k = m
$$

我们可以发现，每个 $\operatorname{Res}(x)$ 都是一个大小为 $r$ 的有序数组。之后我们会证明：对于

$$
x \equiv a \pmod m
$$

的所有可能的取值

$$
0 \leq a < m
$$

有序数组 $\operatorname{Res}(x)$ 都是唯一的。

这就意味着：我们可以通过先获得 $\operatorname{Res}(x)$ ，再去「查表」（查剩余系表），找到这个有序数组所对应的同余数，就能得到答案。

那么，这个为什么可以更加方便地计算模数 加、减、乘 呢？

因为根据同余的运算法则，我们可以轻松地得到如下结论：

对于

$$
\operatorname{Res}(x) = (x \bmod m_1, \cdots ,x \bmod m_r)
$$

$$
\operatorname{Res}(y) = (y \bmod m_1, \cdots ,y \bmod m_r)
$$

我们有：

$$
\begin{aligned}
& \operatorname{Res}(x+y) \\
=& ((x+y) \bmod m_1, \cdots ,(x+y) \bmod m_r) \\
=& ((x\bmod m_1+y\bmod m_1)\bmod m_1, \cdots ,(x\bmod m_r+y\bmod m_r)\bmod m_r) \\
=& \operatorname{Res}(x) \oplus \operatorname{Res}(y)
\end{aligned}
$$

$$
\begin{aligned}
& \operatorname{Res}(x-y) \\
=& ((x-y) \bmod m_1, \cdots ,(x-y) \bmod m_r) \\
=& ((x\bmod m_1-y\bmod m_1) \bmod m_1, \cdots ,(x\bmod m_r-y\bmod m_r)\bmod m_r) \\
=& \operatorname{Res}(x) \ominus \operatorname{Res}(y)
\end{aligned}
$$

$$
\begin{aligned}
& \operatorname{Res}(x\times y) \\
=& ((x\times y) \bmod m_1, \cdots ,(x\times y) \bmod m_r) \\
=& ((x\bmod m_1\times y\bmod m_1)\bmod m_1, \cdots ,(x\bmod m_r\times y\bmod m_r)\bmod m_r) \\
=& \operatorname{Res}(x) \otimes \operatorname{Res}(y)
\end{aligned}
$$

我们分别定义 $\oplus, \ominus, \otimes$ 为逐元素模数运算。

P106 独立剩余为什么能这么做？

我们来证明为何 有序数组 和 同余数 能够一一对应。

对于

$$
\operatorname{Res}(x) = (x \bmod m_1, \cdots ,x \bmod m_r)
$$

如果存在一个 $y$，使得

$$
\operatorname{Res}(x) = \operatorname{Res}(y)
$$

那么其等价于 $x \equiv y \pmod m$.

证明：

$$
x\equiv y \pmod m
$$

等价于

$$
x\equiv y \pmod {m_1}
$$

$$
x\equiv y \pmod {m_2}
$$

$$
x\equiv y \pmod {m_3}
$$

$$
\cdots
$$

$$
x\equiv y \pmod {m_r}
$$

由于对于任意的 $m_j \neq m_k$ 有

$$
m_j \perp m_k
$$

根据 $(4.42)$，上述同余方程组的充要条件即为

$$
x \equiv y \pmod {\prod _ k m_k = m}
$$

P106 独立剩余得到同余方程组后怎么办？

查表。除此之外，书上还给出了一种构造方法：通过扩展欧几里得算法将一个数组变成其的某一个特殊的线性组合，而这个线性组合就是我们所想要得到的解。

这里不多做展开这个方法，我们想说的是，除此之外，还可以利用中国剩余定理来获得解，因为本质上我们获得了一堆同余方程组，其模数互相互素。方法也不在这里展开，可能日后会重新写一篇文章。

P106 模数在求解行列式中的应用

在求解行列式的时候，由于行列式的初等变换不会改变其的大小，所以我们会使用高斯消元将行列式所对应的矩阵消元成一个上三角矩阵

$$
\left|\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1 n} \\
0 & a_{22} & \cdots & a_{2 n} \\
\ldots & \cdots & \cdots & \cdots \\
0 & 0 & \cdots & a_{n n}
\end{array}\right| = \prod_k a_{kk}
$$

在这个过程中，我们不可避免地会用到除法，从而可能导致精度的损失（在使用计算机进行计算的时候）。

这个时候，使用模数即模数乘法的逆元便是一个很好的主意。

我们可以证明，乘以逆元然后进行行列式的初等变换可以取得同样的效果，只要最终我们去的素数足够大，不与答案相冲突，我们便能够得到正确的结果。

虽然我也并不知道这与独立剩余有什么关系...