附录6 - 模 $p$ 意义下的多项式

已知： $p$ 是一个素数。集合 $S = \{1, 2, \cdots, p-1\}$ 包含了所有非 $0$ 的系数。
求证： 对于任意给定的 $a \in S$，必然存在唯一的 $x \in S$，使得 $a \cdot x$ 除以 $p$ 的余数为 $1$（即在模 $p$ 意义下， $x$ 是 $a$ 的倒数，记作 $a^{-1}$）。

第一步：证明“存在性”（为什么一定能找到这样一个 $x$？）

为了寻找 $a$ 的倒数，我们把 $a$ 分别乘上集合 $S$ 中的每一个数，得到一组全新的数：
$a \cdot 1, a \cdot 2, a \cdot 3, \cdots, a \cdot (p-1)$
我们现在来观察这 $p-1$ 个乘积除以 $p$ 的余数。关键结论：
这 $p-1$ 个乘积除以 $p$ 的余数，绝不可能相等，且都不为 $0$。

严谨证明（反证法）：
不可能余数为 0： 如果某个乘积 $a \cdot k$ 除以 $p$ 余数为 $0$，说明 $p$ 能够整除 $a \cdot k$。因为 $p$ 是素数，那么 $p$ 要么整除 $a$，要么整除 $k$。但是 $a$ 和 $k$ 都在 $\{1, 2, \cdots, p-1\}$ 之间，它们都比 $p$ 小，显然不可能被 $p$ 整除。矛盾！所以余数绝对不是 $0$。

不可能有两个余数相等： 假设有两个不同的数 $m, n \in S$（不妨设 $m > n$），使得 $a \cdot m$ 和 $a \cdot n$ 除以 $p$ 的余数相同。那么它们的差 $(a \cdot m) - (a \cdot n) = a(m - n)$ 必定能被 $p$ 整除。同样地，因为 $p$ 是素数，它必须整除 $a$ 或者整除 $(m - n)$。如前所述，$p$ 不可能整除 $a$；而 $m$ 和 $n$ 都是 $1$ 到 $p-1$ 之间的数，它们的差 $m-n$ 是一个大于 $0$ 且严格小于 $p$ 的整数，也不可能被 $p$ 整除。矛盾！

通过以上反证法，我们得出一个极其漂亮的结论：这 $p-1$ 个乘积除以 $p$ 的余数，既不为 $0$，也互不相同。既然余数的取值范围只能是 $\{1, 2, \cdots, p-1\}$，刚好也是 $p-1$ 个可能的值，而我们这里又产生了 $p-1$ 个互不相同的余数。根据抽屉原理，这 $p-1$ 个余数与 $\{1, 2, \cdots, p-1\}$ 必须是一一对应的关系（只是顺序打乱了而已）。

因此，在这 $p-1$ 个余数中，必定有且仅有一个余数等于 1。产生这个余数 $1$ 的那个乘数，就是我们要找的倒数 $x$（即 $a^{-1}$）。存在性得证。

第二步：证明“唯一性”

虽然前面的抽屉原理已经暗示了唯一性，但我们可以用一个更具代数美感的方法来补充证明。假设 $a$ 有两个倒数 $x$ 和 $y$，即在模 $p$ 运算下：$a \cdot x = 1$ 且 $a \cdot y = 1$那么根据模 $p$ 运算满足乘法结合律和交换律，我们可以这样推导：
$x = x \cdot 1 = x \cdot (a \cdot y) = (x \cdot a) \cdot y = (a \cdot x) \cdot y = 1 \cdot y = y$
所以 $x$ 必然等于 $y$。唯一性得证。

虽然我们刚刚证明了乘法逆元存在且唯一，但是并没有给出求逆元的方法，实际计算中可以通过“穷举法”来计算：因为 $\mathbb{Z}_p$ 中只有 $p - 1$ 个元素，所以最多计算 $p - 1$ 次，就一定可以找到乘法逆元。

如果模数不是素数，比如模 4（系数范围是 0, 1, 2, 3）：
尝试寻找 $2$ 的倒数。
$2 \times 1 = 2$ （余2）
$2 \times 2 = 4$ （余0）
$2 \times 3 = 6$ （余2）
你会发现，无论 $2$ 乘以什么，余数都不可能是 $1$！这意味着在模 4 的规则下，$2$ 是没有倒数（不能作除法）的，所以 $\{0, 1, 2, 3\}$ 无法构成一个数域。

带余除法、辗转相除法求最大公约式、多项式的裴蜀定理、因式定理、欧几里得引理、唯一分解定理，对模 $p$ 意义下的多项式都 完美适用。证明它们的本质还是带余除法，只要最高次项的系数之间能作除法且商唯一，这些定理就都能无缝迁移。

需要特别说明的是，模 $p$ 的多项式中，高斯引理不再有意义，因为两个系数的“最大公约数”不再有意义。模 $p$ 下任意一个非 0 数 $a$ 都可以整除另一个非 0 数 $b$（$\div b = \times b^{-1}$），因此高斯引理中关于「本原多项式」的定义在模 $p$ 下不再有意义了。
（但是两个多项式的「最大公约式」和「裴蜀定理」在模 $p$ 下依然是定义良好的，不要混淆）

因为任意的整数 $a$、$b$，都有:
$(a + b)\mod p = ((a\mod p) + (b\mod p))\mod p$
$(ab)\mod p = ((a\mod p)(b\mod p))\mod p$
因此在一般多项式中成立的等式，只要满足：

1. 参与运算的系数都是整数
2. 只包含乘、加运算

就都可以无缝移植到模 $p$ 意义的多项式中

『新生之梦定理』：
在模素数 $p$ 的多项式系统（或有限域 $\mathbb{Z}_p$）中，对于任意多项式 $f(x)$ 和 $g(x)$，都有：

$(f(x) + g(x))^p = f(x)^p + g(x)^p$

简单来说，在模 $p$ 下，和的 $p$ 次方，等于 $p$ 次方的和。所有的交叉项神奇地全部消失了！

（刚接触多项式的“新生”总是容易错误的写 $(x + y)^p = x^p + y^p$，模 $p$ 下这个等式神奇的成立了，因此这个定理叫“新生之梦”）

证明：
为了书写简便，我们用变量 $a$ 和 $b$ 来代替多项式 $f(x)$ 和 $g(x)$。
第一步：写出二项式展开
根据二项式定理，我们将 $(a + b)^p$ 完全展开：

$(a + b)^p = a^p + C_p^1 a^{p-1}b + C_p^2 a^{p-2}b^2 + \cdots + C_p^{p-1} ab^{p-1} + b^p$

在这个展开式中，第一项是 $a^p$，最后一项是 $b^p$。我们要证明“新生之梦”成立，等价于证明：中间所有的 $p-1$ 个交叉项，在模 $p$ 的意义下全部等于 $0$。而中间这些项的系数，统一可以表示为组合数 $C_p^k$ （其中 $1 \le k \le p-1$）。所以我们的核心任务就变成了证明：当 $1 \le k \le p-1$ 时，$C_p^k$ 能被 $p$ 整除。

第二步：攻克组合数 $C_p^k$
我们将组合数 $C_p^k$ 按照阶乘的定义展开：

$C_p^k = \frac{p!}{k!(p-k)!}$

将其移项，写成乘积的形式（为了避免分数带来的整除性困扰）：

$C_p^k \cdot k! \cdot (p-k)! = p!$

把右边的 $p!$ 拆开：

$C_p^k \cdot k! \cdot (p-k)! = p \cdot (p-1)!$

现在，仔细观察这个等式：等式右边 明显包含因子 $p$，所以等式右边一定能被 $p$ 整除。等式左边 是三个整数连乘，既然右边能被 $p$ 整除，左边也必须能被 $p$ 整除。最关键的逻辑（欧几里得引理的体现）： $p$ 是一个素数。如果一个素数能整除几个数的乘积，它必须至少能整除其中一个。我们来看看 $k!$ 和 $(p-k)!$：$k! = 1 \times 2 \times \cdots \times k$。因为 $k < p$，所以 $k!$ 里面全都是比 $p$ 小的正整数。由于 $p$ 是素数，它不可能被任何比它小的正整数整除（更不可能被它们的乘积整除）。同理，$(p-k)!$ 里面也全都是比 $p$ 小的正整数，也不能被 $p$ 整除。既然 $p$ 无法整除 $k!$，也无法整除 $(p-k)!$，那它只能去整除 $C_p^k$ 了！

第三步：得出最终结论
我们证明了：对于所有 $1 \le k \le p-1$，组合数 $C_p^k$ 都是 $p$ 的倍数。在模 $p$ 的运算规则下，任何 $p$ 的倍数都等价于 $0$。因此，二项式展开式中间的所有项：

$C_p^1 a^{p-1}b \equiv 0 \pmod p$

$C_p^2 a^{p-2}b^2 \equiv 0 \pmod p$

$\cdots$

$C_p^{p-1} ab^{p-1} \equiv 0 \pmod p$

中间项全部灰飞烟灭，只留下光秃秃的首尾两项：

$(a + b)^p \equiv a^p + b^p \pmod p$

证明完毕！

特别说明，以上证明都建立在 $p$ 是素数的基础上，如果 $p$ 不是素数，例如计算 $(a + b)^4$ ，中间项系数：$C_4^2 = 6$。而在模 $4$ 下，$6 \equiv 2$，它并不等于 $0$，“新生之梦”不再成立。