费马小定理证明
费马小定理定义：假如p是质数，且gcd(a,p)=1，那么a^(p-1)≡1（mod p），就是说，如果p是质数，并且a与p互质，那么a的p-1次方膜上p恒等于1。下面给出证明：
例如：13是一个质数，那么1,2,3,4,5,6,7,8,9,10,11,12乘上一个与13互质的数，比如乘上3，得到3,6,9,12,15,18,21,24,27,30,33,36,
然后膜上13得到3,6,9,12,2,5,8,11,1,4,7,10，给这些数排序就会发现，他们就是1,2,3,4,5,6,7,8,9,10,11,12，也就是12的阶乘12!，
再将{3,6,9,12,15,18,21,24,27,30,33,36}提取公因式3得到3^(12)*12!%13, ≡12!，两边同时除以12!，就得到3^(12)%13≡1，
最后将3和13换成a，p就得到费马小定理，a^(p-1)%p≡1，也就是a^(p-1)≡1（mod p）。
原文：http://www.cnblogs.com/wuwangchuxin0924/p/7225216.html