Fermat小定理的证明（摘自Matrix67大牛的blog）

这两天一直在看数论，看到miller-rabin素数检测就卡住了，先是Fermat小定理的证明就理解不了，今天看了M67大牛的blog才恍然大悟，对大牛的膜拜之情又加深了。。

Fermat's Litter Theorem:如果p是素数，a是小于p的正整数，则a^(p-1) mod p = 1;

对于这个定理首先我们证明a，2*a,3*a,4*a....(p-1)*a模p的值是1..(p-1)数的排列.

反证法：如果存在n,m(n>m)使n*a ≡m*a(mod p)则p | (n-m)*a,即(n-m)和a中至少有一个因子p，又因为(n-m)和a都小于p所以上述结论不成立，即原定理成立。

由上定理可得(p-1)! ≡ a * 2 * a * ... (p-1) * a (mod p)

因为 (p-1)! ≡ 1 (mod p)所以 等式两边可都除以(p-1)!,得

1≡a^(p-1)(mod p)即a^(p-1) mod p = 1

fermat小定理得证