内容：设p是一个质数，对任意整数a，有(a^{p} equiv a（mod p ))，如果ap互质，有(a^{p-1} equiv 1 (mod p))。
证明：我只会数学归纳法，其它不会。。
(quad quad) 1. 首先，我们很容易得出 当a=1时，有(1^{p} equiv 1 (mod p ))
(quad quad) 2.假设费马小定理成立，我们要将a成立的情况推向a+1的情况成立
(quad quad) 3.由二项式定理可得
[ (a+1)^{p} =a^{p}+{p choose 1}a^{p-1}+{p choose 2 }a^{p-2}+cdots+{p choose p-1}a+1
]
(quad quad) 而 ({p choose k}=frac{p(p-1)cdots(p-k+1)}{k!}) 所以在mod 意义下的 ({p choose k} equiv 0(mod p)) ,所以((a+1)^{p}=a^{p}+1(mod p))
证毕
应用：