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

定义

p是质数，并且gcd(a,p)=1（a,p互质）,那么有
ap−1≡1mod(p)

证明

准备知识

• 剩余类：对模n同余的整数构成的一个集合叫做模n的一个剩余类。
• 简化剩余系（也叫既约剩余系）：模n的值与n互质的全部剩余类中，从每一类中各任取一数所组成的数的集合，叫做模n的一个简化，也叫缩系。
• 完全剩余系：从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系。

剩余系定理2：有整数a，b，c，m为正整数，且gcd(m,c)=1, 则当ac≡bcmod(m)时，有a≡bmod(m).

• 证明：
  • ac≡bcmod(m)=>
  • (a−b)c≡0mod(m)=> （因为gcd(c,m)=1,所以(a−b)为m的倍数）
  • (a−b)≡0mod(m)
  • a≡bmod(m)

剩余系定理7：有一个整数m，且m>1,b是一个整数，且gcd(m,b)=1。如果a1,a2,…,am是模m的一个完全剩余系，那么有ba1,ba2,…,bam是同样是模m的一个完全剩余系。

• 证明：
  • 若存在bai≡bajmod(m)
  • 那么根据剩余系定理2可知，ai≡ajmod(m)
  • 又因为ai，aj同属于一个完全剩余系，所以不会有同余的情况。

证明过程

• 构造素数p的既定剩余系：1，2，…,p−1
• 因为gcd(a,p)=1,所以根据定理7：a，2a，…,(p−1)a也是素数p的一个既定剩余系。
• 那么就有1∗2∗⋯∗(p−1)≡1∗2∗⋯∗(p−1)∗ap−1modp
• 即ap−1≡1mod(p)

应用

• 用来求amod(p)时的逆元，即ap−2.