.png?table=block&id=e721439b-67f8-4fde-8e9a-291fca4d6796&cache=v2)
早几年还在打ACM的时候我就是被数论吊起来打的那类人，没想到退役了偶尔写写还是时常会用到相关的内容。偶尔自己也会忘记原理和实现，干脆另写一篇记录下来。大部分内容来源于IOWIKI。
费马小定理是数论中一个著名的定理，它指出：对于任意质数 $p$ 和任意正整数 $a$，都有 $a^{p-1}\equiv 1\pmod{p}$。
证明如下：
首先，我们知道，对于任意质数 $p$，都有 $p-1$ 个正整数小于 $p$ 且与 $p$ 互质，即 $1,2,3,\dots,p-1$。因此，我们可以写出如下等式：
$$a^{p-1} \equiv (a^{\varphi(p)})^{\frac{p-1}{\varphi(p)}} \equiv 1^{\frac{p-1}{\varphi(p)}} \equiv 1 \pmod{p}$$
其中，$\varphi(p)$ 是欧拉函数，表示小于 $p$ 的正整数中与 $p$ 互质的数的个数。由于 $p$ 是质数，所以 $\varphi(p)=p-1$。
因此，费马小定理得证。