费马小定理

定理内容

若p是质数,且gcd(a,p)=1gcd(a, p) = 1,那么 ap11a^{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×2××(p1)×pA = 1\times 2\times \cdots\times(p-1)\times p,B=x×2x××(p1)x×pxB = x\times 2x\times \cdots\times(p-1)x\times px

那么易知BAB\equiv A(mod p)

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

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

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

感谢你的赞赏!