费马小定理与欧拉定理
贡献者： int256
预备知识 线性同余
，
同余与剩余类，欧拉函数（数论）
，数论求和记号
定理 1 费马小定理
若 $p$ 是素数，且 $p \not{\mid}~ a$，则
\begin{equation}
a^{p-1} \equiv 1 \pmod p ~.
\end{equation}
费马小定理只是费马-欧拉定理的一个特例，我们只要证明了费马-欧拉定理就自动证明了费马小定理。其中，费马-欧拉定理是指：
定理 2 费马-欧拉定理
若 $(a, m) = 1$，则
\begin{equation}
a^{\varphi(m)} \equiv 1 \pmod m ~,
\end{equation}
其中 $\varphi(m)$ 是 $m$ 的欧拉函数。
证明：考虑 $h$ 取遍 $m$ 的一个缩系，则由于 $(a, m) = 1$，利用定理 2 ，$ah$ 也将取遍 $m$ 的一个缩系。这就使得
\begin{equation}
\prod_{h^*(m)}{a h} \equiv \prod _{h^*(m)}h \pmod m ~,
\end{equation}
此处记号使用数论求和的记号，$h^*(m)$ 代表 $h$ 枚举 $m$ 的一个缩系。这式子也就指出
\begin{equation}
a^{\varphi(m)} \prod_{h^*(m)} h \equiv \prod_{h^*(m)} h \pmod m ~,
\end{equation}
而由于 $h$ 取 $m$ 的缩系，故每个 $h$ 都与 $m$ 互质，这必将导致他们的乘积也与 $m$ 互质，从而使得有
\begin{equation}
a^{\varphi(m)} \equiv 1 \pmod m ~.
\end{equation}
证毕！