欧拉定理与费马小定理

 费马小定理：

　　对于质数p，任意整数a，均满足：a^p≡a（mod p）

证明如下：

　　这个可以用欧拉定理来说明：首先，我们把这个式子做一个简单变换得：a^p-1 * a ≡ a（mod p） 因为a ≡ a（mod p）恒成立，所以a^p-1 mod p == 1时费马小定理才成立，又因为p是质数，所以 φn == n-1 ,所以根据欧拉定理：若a，p互质则a^p-1 mod p == 1成立。那么对于a，p不互质，因为p是质数，所以，a一定是倍数a^p ≡ a ≡ 0（mod p）。综上所述，费马小定理成立，其实它算是欧拉定理的一个特例。

欧拉定理与费马小定理

原文：https://www.cnblogs.com/F-C-Y/p/12812277.html