数学/数论/费马小定理著名定理

陈述

如果p是素数，对于所有整数a≠0，

$a^{p-1}\equiv 1\mod {p}$

证明

费马小定理有许多证明。

证明 1（双射）

定义一个函数 $f(x)=ax$ (mod p)。令S={1,2,...,p-1}和T=f(S)={a,2a,...,(p-1)a}。我们断言这两个集合在模p下是相同的。

由于所有不等于 0 的整数在模p下都有逆，对于任何整数m，其中 1≤m<p，$f(a^{-1}m)=m$。然后$f$是满射。

此外，如果$f(x)=f(y)$，那么$ax\equiv ay$ 且 $a^{-1}ax\equiv x\equiv y\equiv a^{-1}ay$。然后$f$是单射，并且是S和T之间的双射。

然后，在模p下，S中所有元素的乘积将等于T中元素的乘积，这意味着

$\prod _{k=1}^{p-1}k\equiv \prod _{k=1}^{p-1}ak{\pmod {p}}$ 且

$\prod _{k=1}^{p-1}k\equiv a^{p-1}\prod _{k=1}^{p-1}k{\pmod {p}}$.

然后

$a^{p-1}\equiv 1\mod {p}$.