费马小定理
基本概念：
费马小定理(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(modm)可得(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.如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系.
证明：若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m),根据引理1则有a≡a[j](mod m).根据完全剩余系的定义可知这是不可能的,因此不存在2个整数ba和ba[j]同余.所以ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系.
构造素数P的“ 完全剩余系 ”：
P={1，2，3，…，P-1}
因为（a，p）=1 ，由引理2得：
也是p的一个完全剩余系。由完全剩余系的性质：
即：
同余式两边可约去 ：
得证！！
算法实现：
一般使用的是快速幂实现费马小定理的内容，并且当a是素数时，ap-2是a的逆元。
推荐习题：
HDU 4869
这里补充一下完全剩余系的知识点：
从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系。
例如：
一个数除以4的余数只能是0，1，2，3，{0，1，2，3}和{4，5，-2，11}是模4的完全剩余系。可以看出0和4，1和5，2和-2，3和11模4同余，这4组数分别属于4个剩余类。
完全剩余系的3个性质：
~step by step
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/39000.html