费马小定理
(1)：如果p,c互质,并且a*c≡b*c(mod p)
∴(a*c – b*c) mod p = 0
∴(a-b)*c mod p = 0;
∴(a-b)*c 是p的倍数
∵p,c互质
∴k*p*c mod p = 0 //仔细看，这里的k*p是不是相当与上面的（a-b）?
∴(a-b) = k*p
∴(a-b) mod p = 0
回归正题
我们终于开始费马小定理的证明：
0,1,2,3,4…p-1是p的完全剩余系
∵a,p互质
∴a,2*a,3*a,4*a…….(p-1)*a也是mod p的完全剩余系
∴1*2*3………*(p-1)*a ≡ a*2*a*3*a……(p-1)*a (mod p)
∴ (p-1)! ≡ (p-1)!*a^(p-1) (mod p)
两边同时约去(p-1)!
a^(p-1) ≡ 1 (mod p)
你以为完了吗？不，还没有，我们还可以用欧拉定理来证
对于质数p，任意整数a，均满足：ap≡a（mod p）
证明如下：
这个可以用欧拉定理来说明：
首先，我们把这个式子做一个简单变换得：ap-1 * a ≡ a（mod p）
因为a ≡ a（mod p）恒成立，所以ap-1 mod p == 1 时费马小定理才成立，
又因为p是质数，所以 φn == n-1 ,
所以根据欧拉定理：若a，p互质则ap-1 mod p == 1成立。
那么对于a，p不互质，因为p是质数，所以，a一定是倍数 ap ≡ a ≡ 0（mod p）。
综上所述，费马小定理成立，其实它算是欧拉定理的一个特例。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/205571.html原文链接：https://javaforall.net
