费马小定理与欧拉定理
贡献者： 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}
证毕！
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。