费马小定理
内容
如果$p$是一个质数而整数$a$不是$p$的倍数则有$$a^{p-1} \ \equiv \ 1 \pmod p$$
实质
欧拉定理的一个特殊情况
$$ a^{\phi(p)} = \ a^{p-1} \ \equiv 1 \pmod p $$
证明
[此坑待填]
应用
除法中取模
$$a^{p-1} \ \equiv \ 1 \pmod p \ \ 即 \ \ a^{p-1} \mod p =1 \mod p = \ 1$$
两边同时除以a得到$$a^{p-2} \mod p = a^{-1} \mod p$$那么只需要在需要除以a的地方乘上左式即等价于除以a,这样的好处在于可以不断取模防止溢出
加上快速幂可以快速进行除法取模运算
限制:仅当模数为素数且a不为p倍数
[方法2]: “此坑待填”
验证质数
值得注意的是,满足费马小定理检验的数也不一定是质数,也可能是合数,这种合数叫做卡迈尔数。
不过不满足费马小定理检验的数一定是合数,满足费马小定理是质数的必要非充分条件
