费马小定理

定理内容

若p是质数，且$gcd(a, p) = 1$，那么 $a^{p-1}\equiv 1$(mod p)

证明

我们考虑从1至p的所有整数{1,2，……,p-1,p}

将其中每一项乘上一个与p互质的数x，得到{x,2x,……,(p-1)x,px}

由于p和x互质，那么这些数同余于{1,2，……,p-1,p}

令$A = 1\times 2\times \cdots\times(p-1)\times p$,$B = x\times 2x\times \cdots\times(p-1)x\times px$

那么易知$B\equiv A$(mod p)

又因为$A = (p-1)!$,$B = x^{p-1}\times (p-1)!$

两边同时约去$(p-1)!$

得到$x^{p-1}\equiv 1$(mod p)