标签：le pmod 定理 威尔逊 笔记 times 质数 sum equiv

定理

当且仅当 \(p\) 是质数时， \((p-1)! \equiv -1 \pmod p\) 。

证明

首先对于 \(p < 5\) 时，直接证即可。

对于 \(p \ge 5\) ，分成以下几种情况：

1. \(p\) 为合数但不为质数的平方，则 \(p\) 可以表示成 \(a\times b\) ，其中 \(a,b\) 都是 \(\le p\) 的不同的整数，在 \((p-1)!\) 中出现过，所以 \(ab | (p-1)!\) ，得 \((p-1)! \not\equiv -1 \pmod p\) ，定理成立。

2. \(p\) 为质数的平方，设 \(p=t^2\) ，其中 \(t\) 是小于 \(p\) 的质数，\(\because p \ge 5\) ， \(\therefore t \ge 3\) 。在 \(1\) 到 \(p-1\) 中，\(t\) 作为质因数出现在 \(t\), \(2t\), \(3t \dots t(t-1)\) 之中，共 \(t-1\) 个。\(\because t \ge 3\) ，\(\therefore t-1 \ge 2\) ，\(t^2|(p-1)!\) ，故 \((p-1)! \not \equiv -1 \pmod p\) ，定理成立。

最后一种情况： \(p\) 为质数。则 \((p-1)!=1 \times (p-1) \times [2 \times 3 \times \dots \times(p-2)]\)

\(\because\) \(p \ge 5\) 且 \(p\) 是质数， \(\therefore\) \(2\) 到 \(p-2\) 有偶数个数。假设其中有两个数在模 \(p\) 意义下的逆元相同，设这两个数为 \(a,b\) ，逆元为 \(t\) ，则可得：

\[at \equiv bt \equiv 1\pmod p \]

则 \(p|t(a-b)\) ，\(\because\) \(a,b,t <p\) ， \(\therefore p\not| t\) 且 \(p\not | (a-b)\) ，故 \(p\not |t(a-b)\) ，矛盾。故 \(2\) 到 \(p-2\) 中每个数的逆元各不相同。

再证 \(2\) 到 \(p-2\) 中每个数逆元不为自己，假设 \(k\) 的逆元是它本身，则有

\[k^2\equiv1\pmod p \]

则 \(p|k^2-1\) ，因式分解变成 \(p|(k+1)(k-1)\) ，则 \(p|k+1\) 或 \(p|k-1\) ，解得 \(k=1\) 或 \(k=p-1\) ，都不在 \(2\) 到 \(p-2\) 的范围内，故 \(k\) 不存在。

\(\therefore\) \(2\) 到 \(p-2\) 中每个数模 \(p\) 意义下的逆元互不相同，且不为自己，同时也在 \(2\) 到 \(p-2\) 中，于是：

\[(p-1)!\equiv 1 \times (p-1) \times [2 \times 3 \times \dots \times(p-2)] \equiv p-1\equiv-1 \pmod p \]

得证。

一些题目

(p-k) 的阶乘

注：这个网站可能打不开。

题意：这是一道提交答案题，\(p\) 为质数，设

\[S(p)=\displaystyle\sum_{1\le k<5}(p-k)! \bmod p \]

求 \(\displaystyle\sum_{1 < p<10^8}S(p)\) , \(p\) 是质数。

思路：

我们可以把上面的式子在模 \(p\) 的意义下拆一下：

\[\sum_{1 \le k < 5}(p-k)! \equiv(p-5)! \times(1+(p-4) + (p-4)(p-3)+ (p-4)(p-3)(p-2) + (p-4)(p-3)(p-2)(p-1)) \pmod p \]

看着复杂，但我们是在模 \(p\) 的意义下运算，所以每几个二次二项式的乘积对 \(p\) 取模相当于常数项对 \(p\) 取模，上式变为：

\[\sum_{1\le k < 5}(p-k)! \equiv (p-5)!(1-4+12-24+24) \pmod p \]

\[\sum_{1\le k < 5}(p-k)! \equiv 9(p-5)! \pmod p \]

我们希望 \((p-5)!\) 可以变为 \((p-1)!\) ，这样我们就能和威尔逊定理扯上关系了，于是：

\[\sum_{1\le k < 5}(p-k)! \equiv 9(p-1)! \div[(p-4)(p-3)(p-2)(p-1)] \pmod p \]

\[\sum_{1\le i < 5}(p-k)! \equiv 9(p-1)! \div24 \pmod p \]

\[\sum_{1\le i < 5}(p-k)! \equiv -9 \times 24^{-1} \pmod p \]

于是只用求逆元即可，复杂度 \(O(n \log p)\) ，大概跑个几秒就出来了。

标签：le,pmod,定理,威尔逊,笔记,times,质数,sum,equiv
From： https://www.cnblogs.com/rlc202204/p/16949468.html