费马小定理证明（copy的，自己捋清楚）

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）

证明（copy的百度百科，加点自己的解释）

引理1．
　　若a,b,c为任意3个整数,m为正整数，且(m,c)=1，则当a·c≡b·c(mod m)时，有a≡b(mod m)。
　　证明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。

　　　　　因为(m,c)=1即m,c互质，c可以约去（ x=a-b, x*c=k*m(k∈Z), (c,m)=1, ∴c不提供m的因子, ∴ x=k*m(k∈Z) ），

　　　　　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的一个完全剩余系，则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。
　　证明:(反证)

　　若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)..(i>=1 && j>=1)，

　　根据引理1则有a[i]≡a[j](mod m)。根据完全剩余系的定义可知这是不可能的，

　　因此不存在2个整数 b·a[i]和b·a[j]同余。所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模m的一个完全剩余系。

构造素数 p 的完全剩余系

因为

，由引理2可得

也是p的一个完全剩余系。

由完全剩余系的性质，

即

易知

，

同余式两边可约去

( 如引理1 ),

得到

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

巴特西