book
归档: OI 
flag
mode_edit

定理内容

$$
p是素数\Leftrightarrow (p-1)!\equiv-1\ (\text{mod}\ p)
$$

证明(口胡)

考虑$[1,p-1]$内的所有整数,他们在$\text{mod}\ p$意义下一定是有逆元的,且他们的逆元一定是小于等于p的

对于上面小结论的证明

由于$p$是素数,我们可以用exgcd构造出方程$ax+bp=\gcd(a,p)$一组解,因此,$[1,p-1]$的整数中,他们一定是有逆元的。

不妨设$a\cdot a^{-1}\equiv1\ \text{mod}\ p$,若$a^{-1}>p$则有,$a\cdot(p+q)\equiv1\ \text{mod}\ p$。

这样以来,我们便得到了一个更小的逆元,原命题得证

然后我们考虑,由于每个数的逆元都是唯一的,如果$p​$是个,偶数,那么,$[1,p-1]​$内的数可以两两配对,与他的逆元相乘得到1,但是注意到,大于2的质数都是奇数。所以当这些数两两配对之后,一定会剩下一个,那么剩下的那个是什么呢?

注意到有一些数的逆元是它自身,这样就没人和他配对了,不妨设$a^2\equiv1$

然后我们就知道$a=1或a=-1$,这样就好办啦

在$[1,p-1]$中,除了$p-1$之外的数相乘都是1,那么$(p-1)!\equiv p-1\equiv-1$

于是就得证口胡成功啦

navigate_before navigate_next