威尔逊定理

定义

Wilson 定理：对于素数 有 。

证明

我们知道在模奇素数 意义下， 都存在逆元且唯一，那么只需要将一个数与其逆元配对发现其乘积均为（同余意义下），但前提是这个数的逆元不等于自身。那么很显然 就是逆元等于其自身的数的乘积，这两个数为 。在 为 时单独讨论即可。

对于整数 ，令 表示所有小于等于 但不能被 整除的正整数的乘积，即 。

Wilson 定理指出 且可被推广至模素数 的幂次。

阶乘与素数

在某些情况下，有必要考虑以某个素数 为模的公式，包含分子和分母中的阶乘，就像在二项式系数公式中遇到的那样。

只有当阶乘同时出现在分数的分子和分母中时，这个问题才有意义。否则，后续项 将减少为零。但在分数中，因子 可以抵消，结果将是非零。

因此，要计算 ，而不考虑阶乘中出现因数 。写下素因子分解，去掉所有因子 ，并计算乘积模。

用 表示这个修改的因子。例如：

通过学习如何有效地计算这种修正的阶乘，可以快速计算各种组合公式的值。

计算余数的算法

计算上述去掉因子 的阶乘模 的余数。

可以清楚地看到，除了最后一个块外，阶乘被划分为几个长度相同的块。

块的主要部分 很容易计算，可以应用 Wilson 定理：

总共有 个块，因此需要将 写到 的指数上。可以注意到结果在 和 之间切换，因此只需要查看指数的奇偶性，如果是奇数，则乘以 。除了使用乘法，也可以从结果中减去 。

最后一个部分块的值可以在 的时间复杂度单独计算。

这只留下每个块的最后一个元素。如果隐藏已处理的元素，可以看到以下模式：

这也是一个修正的阶乘，只是维数小得多。它是：

因此，在计算修改的阶乘 中，执行了 个操作，剩下的是计算 ，于是有了递归，递归深度为 ，因此算法的总时间复杂度为 。

如果预先计算阶乘 模 ，那么时间复杂度为 。

计算余数算法的实现

具体实现不需要递归，因为这是尾部递归的情况，因此可以使用迭代轻松实现。在下面的实现中预计算了阶乘：

因此有时间复杂度 。如果需要多次调用函数，则可以在函数外部进行预计算，于是计算 拥有 的时间复杂度。

如果空间有限，无法存储所有阶乘，也可以只存储需要的阶乘，对它们进行排序，然后计算阶乘 而不显式存储它们。

阶乘中素数的个数

如果想计算二项式系数模 ，那么还需要考虑在 的阶乘的素因子分解中 出现的次数，或在计算修改因子时删除因子 的个数。

Legengre 在 1808 年提供了一个公式，可以在 时间复杂度计算 的个数 。指出 中含有的素数 的幂次为：

证明：将 记为 那么其中 的倍数有 然后在 中继续寻找 的倍数即可，这是一个递归的过程。为了方便记 。

因此得到实现：

很容易证明，这个公式与前面的部分使用了相同的想法。删除所有不包含因子 的元素，保留元素 。从它们中移除因子 ，可以得到乘积：

然后再次得到递归。

另一种其他地方比较常见的公式，用到了 p 进制下各位数字和：

与等比数列求和公式很相似。由于涉及各位数字和，利用数学归纳法可以轻松证明。

特别地，阶乘中 2 的幂次是：

Kummer 定理

组合数对一个数取模的结果，往往构成分形结构，例如谢尔宾斯基三角形就可以通过组合数模 2 得到。

如果仔细分析，p 是否整除组合数其实和上下标在 p 进制下减法是否需要借位有关。这就有了 Kummer 定理。

Kummer 定理：p 在组合数 中的幂次，恰好是 p 进制下 m 减掉 n 需要借位的次数。

特别地，组合数中 2 的幂次是：

Wilson 定理的推广

对于素数 和正整数 有 。

依然考虑配对一个数与其逆元，也就是考虑关于 的同余方程 的根的乘积，当 时方程仅有一根，当 且 时有四根为 其他时候则有两根为 。

至此我们对 Wilson 定理的推广中的 有了详细的定义即

下文两个推论中的 ，均特指这样的定义：当模数 取 及以上的 的幂时取 ，其余取 。

推论 1

对于素数 、正整数 、非负整数 和 有 。

???note "证明" 证明：令 表示不能被 整除的数的乘积，有

$$
\begin{aligned}
(n!)_p&=\prod_{1\leq r\leq n}'r\\
&=\left(\prod_{i=0}^{\lfloor n/p^q \rfloor -1}\prod_{1\leq j\leq p^q}'(ip^q+j)\right)\left(\prod_{1\leq j\leq N_0}'(\lfloor n/p^q\rfloor p^q+j)\right)\\
&\equiv ((p^q!)_p)^{\lfloor n/p^q\rfloor}(N_0!)_p\\
&\equiv (\pm 1)^{\lfloor n/p^q\rfloor}(N_0!)_p\pmod{p^q}
\end{aligned}
$$

将 $1\times 2\times 3\times \cdots \times n$ 记为 $(0\times p^q+1)\times (0\times p^q+2)\times \cdots \times (\lfloor n/p^q\rfloor p^q+N_0)$ 就得到了上述第二行。

至此得到了

推论 2

对于素数 和正整数 和非负整数 有

其中 而 与上述相同。

记 且 有

右边的分母中括号内的项均在模 意义下均存在逆元，可直接计算，而 的与上述相同。

例题

本页面主要译自博文 Вычисление факториала по модулю 与其英文翻译版 Factorial modulo p。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。