【学习总结】数学-费马小定理

2019-04-13 16:12发布

定义

p是质数,并且gcd(a,p)=1(a,p互质),那么有
ap11mod(p)

证明

准备知识
  • 剩余类:对模n同余的整数构成的一个集合叫做模n的一个剩余类。
  • 简化剩余系(也叫既约剩余系):模n的值与n互质的全部剩余类中,从每一类中各任取一数所组成的数的集合,叫做模n的一个简化,也叫缩系。
  • 完全剩余系:从模n的每个剩余类中各取一个数,得到一个由n个数组成的集合,叫做模n的一个完全剩余系。
剩余系定理2:有整数a,b,c,m为正整数,且gcd(m,c)=1, 则当acbcmod(m)时,有abmod(m).
  • 证明:
    • acbcmod(m) =>
    • (ab)c0mod(m) => (因为gcd(c,m)=1,所以(ab)m的倍数)
    • (ab)0mod(m)
    • abmod(m)
剩余系定理7:有一个整数m,且m>1,b是一个整数,且gcd(m,b)=1。如果a1,a2,,am是模m的一个完全剩余系,那么有ba1,ba2,,bam是同样是模m的一个完全剩余系。
  • 证明:
    • 若存在baibajmod(m)
    • 那么根据剩余系定理2可知,aiajmod(m)
    • 又因为aiaj同属于一个完全剩余系,所以不会有同余的情况。
证明过程
  • 构造素数p的既定剩余系:12,p1
  • 因为gcd(a,p)=1,所以根据定理7:a2a,(p1)a也是素数p的一个既定剩余系。
  • 那么就有12(p1)12(p1)ap1modp
  • ap11mod(p)

应用

  • 用来求amod(p)时的逆元,即ap2.