Fork me on GitHub

费马小定理

定理内容

若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)

感谢你的赞赏!