Home Categories Archives Friends GitHub

基于费马小定理的质数筛选方法

C++ 数学, C++

费马小定理

假设 aa 为一个整数,pp 为一个质数,那么 apaa^p-aaa 的倍数,即 aqa(modp)a^q\equiv a\pmod p 如果 aa 不是 pp 的倍数,那么这个定理可以写成更为常用的一种形式 ap11(modp)a^{p-1}\equiv 1 \pmod p 费马小定理的逆定理不成立,假设 apaa^p-aaa 的倍数,那么 pp 不一定是一个质数。

证明

// TODO