费马小定理是初等数论四大定理（威尔逊定理，欧拉定理，中国剩余定理和费马小定理）之一。
费马小定理：若p是质数，且a,p互质，则a^(p-1) ≡ 1 mod p.
证明：
1)ax≡bx(mod p),且x,p互质，则a≡b(mod p)
2){1,2,3……,p-1} = {a mod p, 2a mod p, 3a mod p, ……(p-1)a mod p}
证：i ≠ j, (1≤i,j≤p-1,p是质数)则ia ≠ ja (mod p) 由1)得证
3)1*2*3*……*p-1 (mod p) ≡ a*2a*3a*……*(p-1)a (mod p) 化简，得a^(p-1) ≡ 1 mod p
作用——质数测试：
pick some a → a^(p-1) ≡ 1 mod p →测试p是否为质数
若a^(p-1) ≡ 1 mod p成立，p不一定是质数（卡米克尔数，概率很小）
若a^(p-1) ≡ 1 mod p不成立，p一定不是质数