威尔逊定理
蒟蒻君HJT
·
·
个人记录
自己想的。手玩样例是好文明。
威尔逊定理：对于质数 p，(p-1)! \equiv -1 \pmod p
以下省略 \pmod p。
$p>2$，则 $p$ 为奇数，考虑每个 $i\in[p-1]$ 的 $\pmod p$ 意义下的逆元。两个数 $i,j$ 逆元不能相同，否则 $i^{-1}\equiv j^{-1}\Rightarrow i\equiv j$。$1,p-1$ 的逆元显然分别是 $1,p-1$，对于 $i\in[2,p-2]$，猜测他们的逆元也都为 $[2,p-2]$ 中的其他数且不重复。不重复性已经证明过了。$1$ 和 $p-1$ 已经被自身占据了，所以不会是 $1$ 和 $p-1$，只需要证明 $i\in[2,n]$ 的逆元不是自身。
如果是自身，$i^2\equiv 1$ 和 $1^2\equiv 1$ 作差得 $(i-1)(i+1)\equiv 1$，模数是质数，说明 $(i-1),(i+1)$ 其中一个必须是 $p$ 的倍数，但是 $i\in[2,p-2]$ 所以这是不可能的。由此可得：$i\in[2,p-2]$ 的逆元都为 $[2,p-2]$ 中的其他数且不重复，配对相乘，可得 $\displaystyle\prod_{i=2}^{p-1}i\equiv 1$，所以 $\displaystyle\prod_{i=1}^{p-1}i\equiv -1$。