您的位置: 首页 > 文章 > 欧拉定理 欧拉定理 分类: 文章 • 2024-07-23 18:20:04 费马小定理:如果一个P是素数,并且:gcd(a,p)==1.那么:(a^P)%P==a;//反向利用这个定理可以证明一个数是不是素数(多个a) 欧拉定理{ 欧拉函数:φ(n) 表示从1到n-1与n互质的数的个数 则( a ^φ(n) )%n=1。称为欧拉定理(特别的当n为素数的时候,φ(n)==n-1) } 欧拉降幂公式{ (快速幂取模时,指数爆炸的情况) }