费马小定理

　

费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

验证推导

引理1．

若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(mod m)时,有a≡b(mod m)

证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a– b≡0(mod m)可得a≡b(mod m)

引理2．

设m是一个整数,且m>1,b是一个整数且(m,b)=1.如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.

证明:若存在2个整数ba[i]和ba[j]同余即ba[i]≡ba[j](mod m)..(i>=1 && j>=1),根据引理1则有a[i]≡a[j](mod m).根据完全剩余系的定义可知这是不可能的,因此不存在2个整数ba[i]和ba[j]同余.所以ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.

构造素数

 

的完全剩余系

因为

 

，由引理2可得

也是p的一个完全剩余系。由完全剩余系的性质，

即

易知

 

，同余式两边可约去

 

，得到

这样就证明了费马小定理。

文章最后发布于: 2017-09-28 06:46:06

相关阅读

scikit-learn机器学习（五）--条件概率，全概率和贝叶斯定理

在理解贝叶斯之前需要先了解一下条件概率和全概率，这样才能更好地理解贝叶斯定理 一丶条件概率 条件概率定义：已知事件A发生的条

墨菲定律、二八法则、马太效应、手表定理、“不值得”

墨菲定律、二八法则、马太效应、手表定理、“不值得”定律、彼得原理、零和游戏、华盛顿合作规律、酒与污水定律、水桶定律、蘑菇

大数定理和中心极限定理

Season请你思考：·大数定理与概率是否有关系？·中心极限定理和极限有什么关系？·大数定理和中心极限定理之间是否有关系？从上面这个公

欧拉定理及推论

链接：https://ac.nowcoder.com/acm/contest/330/E来源：牛客网 有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定

三个重要的同余式——威尔逊定理，费马小定理，欧拉定理（扩

鸣谢synapse7大大 威尔逊定理 (p−1)!≡p−1≡−1   (mod p) (p