费马小定理

如果p是质数，并且a,p互质，那么\(a^{p-1}=1\pmod{m}\)

证明：

我们需要先构造一个与p互质的数列\(A={1,2,3,\cdots,p-1}\).然后想办法往我们的目标去靠拢，于是我们接下来只需要证明:\(\prod_{i=1}^{p-1}a*A_i=\prod_{i=1}^{p-1}A_i\pmod{m}\),

然后我们只需要证明\(a*A_i和A_i的余数是一样的就说明恒成立,也就是需要证明a*A_i的每个余数都是不一样的\)

我们可以使用反证法来证明，也就是如果是一样，那么:\(a*A_i=px+r,a*A_j=py+r;\)

两式相减就会发现：\(a*(A_i-A_j)=p(x-y)\),但是很显然a和\(A_i-A_j\)都不是p的倍数，所以显然不成立。

接下来原式子：\(a^{p-2}\prod_{i=1}^{p-1}A_i=\prod_{i=1}^{p-1}A_i\pmod{p}\)

所以得证。