欧拉定理

一、知识点

1. 欧拉定理：若 $a$ 与 $n$ 互质，则 $a^{\phi(n)} \equiv 1\;(mod\;\;n)$

证明

在 $1 \sim n$ 中，与 $n$ 互质的数的个数为 $\phi(n)$，设他们为 $S = \{a_1, a_2, \ldots , a_{\phi(n)}\}$，其两两互不相同。

(1) 构造新集合：用 $a$ 乘以 $a_1, a_2, \ldots , a_{\phi(n)}$ 中的每个元素，得到 $aS = \{a \cdot a_1, a \cdot a_2, \ldots , a \cdot a_{\phi(n)}\}\;mod\;n$。

因为 $a$ 和 $n$ 互质，根据乘法同余定理，集合 $aS$ 中的每个元素模 $n$ 的结果仍然是两两互不相同的，并且都与 $n$ 互质。

(2) 证明集合相等：因此，由于 $S$ 和 $aS$ 中的元素在模 $n$ 下两两不同且都与 $n$ 互质，我们可以得出 $aS$ 和 $S$ 实际上是相同的集合（尽管元素的顺序可能不同），即它们包含相同数量的与 $n$ 互质的元素（且与 $n$ 互质的元素就这 $\phi(n)$ 个），而且每个元素都是互不相同的。

(3) 乘积同余：考虑集合 $S$ 和集合 $aS$ 中元素的乘积，有 $\prod S \equiv \prod aS \mod n$ 。由于 $aS$ 和 $S$ 是相同的集合，我们可以将 $\prod aS$ 写成 $a^{\phi(n)} \prod S$ 。因此，我们有 $a^{\phi(n)} \prod S \equiv \prod S \mod n$ 。

(4)约去乘积：由于 $\prod S$ 是与 $n$ 互质的数的乘积，且 $gcd(\prod S, n) = 1$ ，我们可以两边同时约去 $\prod S$ （在模 $n$ 下这是合法的操作），从而得到 $a^{\phi(n)} \equiv 1 \mod n$，得证。

2. 费马小定理：若 $a$ 与 $p$ 互质，且 $p$ 为质数，则 $a^{p - 1} \equiv 1\;(mod\;\;p)$

证明

若 $p$ 为质数，则 $\phi(p) = p - 1$，带入欧拉定理即可。