费马小定理

若p是质数，a与p互质，那么$a^{p-1}\equiv 1\pmod{p}$
等价于$a^p\equiv a\pmod{p}$

前置知识：

完全剩余系
剩余类
完全剩余系引理
m是一个大于1的整数，a是整数且$(m,a)=1$,如果$\{b[i]\}(i\in[1,m])$是模m的一个完全剩余系，则$\{a\times b[i]\}$也是模m的一个完全剩余系
证明：
假设存在两个整数满足$a\times b[i],a\times b[j]$同余，那么
$\qquad a\times b[i]\equiv a\times b[j]\pmod{m}$
由同余的性质（8）可知
$\qquad b[i]\equiv b[j]\pmod{m}$
此时与我们的完全剩余系定义矛盾
由此得证

证明：

可知p是一个大于1的素数，可知一个模p的完全剩余系$\{i\}(i\in [1,p-1])$,
当p与a互质时，我们可以找到一个不大于p的唯一整数j，满足
$\qquad i\equiv a\times j\pmod{p}$
且j与唯一的i对应
或者说，对于我们已知的完全剩余系$\{i\}(i\in [1,p-1])$,
存在$\{i\times a\}(i\in [1,p-1])$也是模p的完全剩余系
将一一对应的每一个方程相乘
$\qquad (p-1)!\equiv (p-1)!\times a^{p-1}\pmod{p}$
p是质数，与(p-1)!互质，根据性质八可知
$\qquad a^{p-1}\equiv 1\pmod{p}$

费马小定理求逆元

逆元