如果p是一个质数，且a不是p的倍数（即$ gcd(a,p)=1 $），那么

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

使用构造集合法证明

定义集合S为：

$ S={ 1,2,\cdots ,p-1} $

该集合中共有$ p-1 $个原色

定义集合T

将集合S中的每一个元素都乘以a，得到新集合T：

$ T={ a,2a,\cdots ,a(p-1)} $

接下来需要证明集合T中的原色在模p下的意义就是集合S的一个重新排列，只需证明：

1.T中没有原色能被p整除

2.T中没有两个元素在模p下相等

对于1.

T中的任意元素表现形式为$ ka,k\in [1,p) $

因为p是质数，且$ k<p $，所以$ p\nmid k $

已知$ p\nmid a $

根据欧几里得引理，如果质数p不整除k也不整除a，那么$ p\nmid (ka) $

因此，T中没有元素能被p整除

对于2.

反证法：假设T中有两个不同的元素$ xa $和$ ya $（其中$ 1\leq x<y\leq p-1 $），它们在模p下相等，就有

$ xa\equiv ya(\mod p) $

因为$ gcd(a,p)=1 $，所以可以使用“消去律”两边同时除以a，得到

$ x\equiv y(\mod p) $

因为x，y都是p的余数，所以当且仅当$ x=y $时满足条件

这与x,y的取值范围矛盾，所以T中没有两个元素在模p下相等

根据S,T和p的关系，我们即可得到同余方程：

$ \prod_{t\in T} t=\prod_{s\in S} s(\mod p) $

化简可得：

$ (a\cdot 1)\times (a\cdot 2)\times \cdots \times (a\cdot (p-1))\equiv 1\times 2\times \cdots \times (p-1)(\mod p) $

$ a^{p-1}\times (p-1)!\equiv (p-1)!(\mod p) $

记$ K=(p-1)! $

等式变为：$ a^{p-1}K\equiv K(\mod p) $

因为p是质数，$ (p-1)! $中不包含因子p，所以$ gcd(K,p)=1 $

两边同时消去K可得：

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

证毕

在密码学中的常用推广形式：

两边同时乘以a，可得：

$ a^p\equiv a(\mod p) $

原文链接：https://www.yuque.com/fragrantveget/ucxpnh/wkc4703mgk7z2g9t?singleDoc# 《费马小定理（Fermat’s Little Theorem）》