注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注，也是习题 4.32 的答案。

欧拉定理

欧拉定理是费马小定理的推广。

$$
a^{\varphi(m)} \equiv 1 \pmod m, a \perp m
$$

证明

在书中的 4.8 节中，我们已经证明了：若 $a \perp m$，则

$$
0 \bmod m, a \bmod m, 2a \bmod m, \cdots, (m-1)a \bmod m
$$

为

$$
0, 1, 2, \cdots, m-1
$$

的一个排列。

这里我们要证明一个更强的结论：

$$
\{ka \bmod m \mid k \perp m, 0 \leq k < m\}, a \perp m
$$

为

$$
\{k \mid k \perp m, 0 \leq k < m\}
$$

的一个排列。

我们思考一下我们到底想证明什么。其实就是在原来的数列

$$
0 \bmod m, a \bmod m, 2a \bmod m, \cdots, (m-1)a \bmod m
$$

中，我们想证明当倍数 $k \perp m$ 时，$ka \bmod m$ 也与 $m$ 互素。

接下来我们给出这个引理的证明：

对于 $0 \leq k < m$，若 $\gcd (k, m) = b > 1$，即当 $k, m$ 不互素时：记

$$
ak = ab \frac k b \equiv t \pmod m, 0 \leq t < m
$$

取 $\displaystyle c = \lfloor \frac {ak} {m} \rfloor$

$$
cm + t = ak
$$

$$
cb \frac m b + t = ab \frac k b
$$

$$
t = b \Big (\frac {ak} {b} - \frac {cm} b \Big )
$$

也就是说 $t$ 有 $b$ 这个因子，即

$$
\gcd(t, m) = \gcd(ak \bmod m, m) \geq b > 1
$$

故 $ak \bmod m$ 与 $m$ 不互素。

也就是说，我们证明了：

• 若 $k$, $m$ 不互素，$ak \bmod m$, $m$ 也不互素。

由于 $ak \bmod m$ 是 $k$ 的排列，所以反之也成立，即

• 若 $k$, $m$ 互素，$ak \bmod m$, $m$ 也互素。

所以，

$$
\{ka \bmod m \mid k \perp m, 0 \leq k < m\}, a \perp m
$$

为

$$
\{k \mid k \perp m, 0 \leq k < m\}
$$

的一个排列。

接下来，我们开始证明欧拉定理。

对于

$$
a_1, a_2, \cdots, a_{\varphi(m)}, a_i \perp m
$$

有：

$$
\begin{aligned}
& \prod _i aa_i = a^{\varphi(m)} \prod _i a_i \\
\equiv & \prod _i (aa_i \bmod m) \\
\equiv & \prod _i a_i \pmod m
\end{aligned}
$$

注意：最后的两部就是通过我们前面证明的引理得到的。

所以我们现在有：

$$
a^{\varphi(m)} \prod _i a_i \equiv \prod _i a_i \pmod m
$$

根据欧拉函数的定义：

$$
\forall i \in [1..\varphi(m)] \Rightarrow a_i \perp m
$$

我们有

$$
\prod _i a_i \perp m
$$

所以根据 $(4.37)$，我们可以约去同余式两边的 $\displaystyle \prod_i a_i$，得到

$$
a^{\varphi(m)} \equiv 1 \pmod m
$$

总结与反思

前面看了书上后面的一些论述，突然想到这个引理有更简单的证明方法。

已知

$$
k \perp m
$$

又

$$
a \perp m
$$

根据 $(4.30)$，这两个条件等价于

$$
ak \perp m
$$

等价于

$$
\gcd (ak,m)=1
$$

根据 $(4.4)$ 欧几里得递推式

$$
\gcd (ak, m) = \gcd (ak \bmod m, m) = 1
$$

等价于

$$
ak \bmod m \perp m
$$

引理证毕。