费马小定理 内容： 若存在整数 a , p 且gcd(a,p)=1,即二者互为质数，则有a^(p-1)≡ 1(mod p)。(这里的 ≡ 指的是恒等于，a^(p-1)≡ 1(mod p)是指a的p-1次幂取模与1取模恒等)（不理解的话请留言）
证明： 这里证明较为复杂需要先引出两个定理：
引理一： 若a,b,c为任意3个整数,m为正整数，且gcd(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)。因为gcd(m,c)=1即m,c互质，c可以约去，a– b≡0(mod m)可得a≡b(mod m)
引理二： 设m是一个整数且m>1，b是一个整数且gcd(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={1,2,3,…,p-1}. 因为 ，由引理2可得 A={a,2a,3a,…,(p-1)a}. 也是p的一个完全剩余系。由完全剩余系的性质， 123*…(p-1)≡a2a3a…*(p-1)a(modp). 即 (p-1)!≡(p-1)!*a^(p-1)(modp) 易知 ((p-1)!,p)=1，同余式两边可约去(p-1)!，得到 a^(p-1)≡1(mod p) 这样就证明了费马小定理。
