定理 10.1（欧拉公式）

如果\(\gcd(a,m) = 1\)，则 \[a^{\phi(m)} \equiv 1 \mod m\]

证明过程

至此，我们已经确定了考察的数的正确集合，所以欧拉公式的证明几乎和费马小定理完全一致。

先证明引理：

引理 10.2 如果\(\gcd(a,m) = 1\)，则数\(b_{1}a,b_{2}a,b_{3}a, \cdots , b_{\phi(m)}a \mod m\)与数\(b_{1},b_{2},b_{3}, \cdots , b_{\phi(m)} \mod m\)相同，尽管他们的次序并不相同。

证明：（极尽相似费马小定理的证明）实际上我们是证明了一个弱一些的结论，由于可以确定\(\phi(m) \le m-1\)，当\(m\)为素数时候取等，那么我们不妨假设有\(b_j a \equiv b_k a \mod m\)，做差，由于同余，而\(m \nmid a\)，\(m \mid \vert b_j - b_k \vert\)，而由于前述条件，只能有\(0\)符合条件，则得到\(b_j \equiv b_k \mod m\)，与假设矛盾（应该两两不同余）。引理得证。

后续，构造

\[(b_{1}a) \cdot (b_{2}a) \cdot (b_{3}a) \cdots (b_{\phi(m)}a) \equiv b_1 \cdot b_2 \cdot b_3 \cdots b_{\phi(m)} \mod m\]

提公因式：

\[a^{\phi(m)}B \equiv B \mod m\]

由于每个\(b_i\)与\(m\)互素，所以我们可以两边整体消去\(B\)，得到：

\[a^{\phi(m)} \equiv 1 \mod m\]