附录10 - 欧拉函数

『欧拉函数 $\varphi(n)$』：正整数 $n$ 的欧拉函数 $\varphi(n)$ 定义为，$1\cdots n$ 中和 $n$ 互素的整数的个数。

如果两个正整数 $m$ 和 $n$ 互素（$\gcd(m, n) = 1$），那么它们乘积的欧拉函数，等于它们各自欧拉函数的乘积：
$\varphi(m \cdot n) = \varphi(m)\varphi(n)$

为了严谨证明，我们把 $1$ 到 $m \cdot n$ 这 $mn$ 个数排成一个 $n$ 行 $m$ 列的矩阵：

我们要在这个矩阵里找：有多少个数同时与 $m$ 和 $n$ 互素？（因为与 $mn$ 互素，等价于既与 $m$ 互素，又与 $n$ 互素）。

1. 纵向看（筛选与 $m$ 互素的数）：
   观察第 $k$ 列的数，它们的统一形式是 $j \cdot m + k$（其中 $j$ 是行号减一）。
   根据带余除法和求最大公约数的性质（辗转相除法）：
   $\gcd(j \cdot m + k, m) = \gcd(k, m)$
   这意味着：同一列的数，与 $m$ 的最大公约数全都是一样的，完全由表头的 $k$ 决定。所以，如果 $k$ 与 $m$ 互素，这一整列的数都与 $m$ 互素；如果 $k$ 与 $m$ 不互素，这一整列全都报废。因为表头是从 $1$ 到 $m$，其中与 $m$ 互素的数有 $\varphi(m)$ 个。所以，只有 $\varphi(m)$ 列幸存下来。

2. 纵列内看（筛选与 $n$ 互素的数）：
   现在我们随便挑出幸存的某一列（假设是第 $k$ 列）。这一列的数是：
   $k, m+k, 2m+k, \dots, (n-1)m+k$
   这里有一个极其重要的数论事实：因为 $\gcd(m, n) = 1$，这 $n$ 个数除以 $n$ 的余数，恰好是
   $0, 1, 2, \dots, n-1$ 的一个完整排列（只是顺序打乱了）。
   （严谨证明：假设有两个数同余，即 $j_1 m + k \equiv j_2 m + k \pmod n$，则 $(j_1 - j_2)m$ 能被 $n$ 整除。因为 $m$ 和 $n$ 互素，所以 $n$ 必须整除 $(j_1 - j_2)$。但 $j_1$ 和 $j_2$ 都小于 $n$，所以它们只能相等。这证明了没有两个数余数相同，必定覆盖所有余数。）
   既然这一列数除以 $n$ 的余数构成了 $0$ 到 $n-1$ 的完整排列，那么根据欧拉函数的定义，这一列中恰好有 $\varphi(n)$ 个数与 $n$ 互素。

3. 总结：
   我们有 $\varphi(m)$ 个合格的列，每一列里又有 $\varphi(n)$ 个合格的数。所以，总共既与 $m$ 互素又与 $n$ 互素的数字个数为：$\varphi(m \cdot n) = \varphi(m)\varphi(n)$

核心思路：构造集合的双射
我们要证明，当 $\gcd(m, n) = 1$ 时，$\varphi(m \cdot n) = \varphi(m)\varphi(n)$。
这在代数上等价于证明：与 $mn$ 互素的数的集合，和“与 $m$ 互素的数的集合”及“与 $n$ 互素的数的集合”的笛卡尔积，元素个数完全相等。

我们定义三个集合：
$U_{mn}$：$1$ 到 $mn$ 中与 $mn$ 互素的整数集合（其元素个数为 $\varphi(mn)$）。
$U_m$：$1$ 到 $m$ 中与 $m$ 互素的整数集合（其元素个数为 $\varphi(m)$）。
$U_n$：$1$ 到 $n$ 中与 $n$ 互素的整数集合（其元素个数为 $\varphi(n)$）。
我们的目标是构造一个从 $U_{mn}$ 到 $U_m \times U_n$ 的映射 $f$，并证明它是双射。

第一步：定义映射（从整体到局部）
对于任意 $x \in U_{mn}$，我们定义映射 $f$ 为分别对 $m$ 和 $n$ 取模：
$f(x) = (x \bmod m, x \bmod n)$
这个映射合法吗？因为 $x$ 与 $mn$ 互素，所以 $x$ 必然既与 $m$ 互素，又与 $n$ 互素。根据欧几里得引理的除法性质，$\gcd(x \bmod m, m) = \gcd(x, m) = 1$。因此，$x \bmod m \in U_m$ 且 $x \bmod n \in U_n$。映射 $f$ 确实把 $U_{mn}$ 里的元素准确地送到了 $U_m \times U_n$ 中。

第二步：利用裴蜀定理证明双射（从局部回推整体）
要证明它是双射，我们只需证明：对于任意给定的数对 $(a, b) \in U_m \times U_n$，在 $U_{mn}$ 中都存在且仅存在一个 $x$，使得 $x \equiv a \pmod m$ 且 $x \equiv b \pmod n$。
这时候裴蜀定理闪亮登场！因为 $\gcd(m, n) = 1$，根据裴蜀定理，必然存在整数 $u$ 和 $v$，使得：
$mu + nv = 1$
我们直接用 $u$ 和 $v$ 像拼积木一样“拼”出这个目标 $x$。令：
$x = (a \cdot nv + b \cdot mu) \bmod mn$

1. 验证 $x$ 满足条件：
   模 $m$ 看：因为 $nv = 1 - mu$，所以 $x \equiv a(1 - mu) + 0 \equiv a \pmod m$。
   模 $n$ 看：因为 $mu = 1 - nv$，所以 $x \equiv 0 + b(1 - nv) \equiv b \pmod n$。
   这证明了 $x$ 的存在性。

2. 验证 $x$ 确实在 $U_{mn}$ 中（即 $x$ 与 $mn$ 互素）：
   假设有素数 $p$ 同时整除 $x$ 和 $mn$。因为 $m$ 和 $n$ 互素，$p$ 只能整除 $m$ 或 $n$ 中的一个。不妨设 $p \mid m$。
   既然 $p \mid m$，而 $x \equiv a \pmod m$，这就意味着 $(x - a)$ 是 $m$ 的倍数，于是 $p \mid (x - a)$，再加上 $p \mid x$，所以 $p$ 也必定整除 $a$。但这不可能！因为 $a \in U_m$，它与 $m$ 是互素的，不可能有 $p$ 这个公因子。产生矛盾，说明 $x$ 必然与 $mn$ 互素，$x \in U_{mn}$。

3. 验证唯一性：
   如果在 $1$ 到 $mn$ 之间还有另一个数 $y$ 也满足 $y \equiv a \pmod m$ 且 $y \equiv b \pmod n$。那么 $x - y$ 既能被 $m$ 整除，也能被 $n$ 整除。因为 $m$ 和 $n$ 互素，所以 $x - y$ 必须能被 $mn$ 整除。但在 $1$ 到 $mn$ 的范围内，两个不同的数之差的绝对值必定小于 $mn$，所以它们只能相等（$x = y$）。

结论：通过裴蜀定理，我们完美证明了 $U_{mn}$ 和 $U_m \times U_n$ 之间存在严密的一一对应关系（双射）。既然两个集合可以完美配对，它们的元素个数就必然完全相等。因此：
$\varphi(mn) = \varphi(m) \cdot \varphi(n)$

『欧拉函数的因数和性质』：对于任意正整数 $n$，有 $\sum_{d \mid n} \varphi(d) = n$。（即 $n$ 的所有因数的欧拉函数之和等于 $n$）

证明：
写出 $n$ 个分数：$\frac{1}{n}, \frac{2}{n}, \dots, \frac{n}{n}$。
将它们全部分解为最简分数。约分后，分母 $d$ 必定是 $n$ 的某个因数，且分子 $k$ 与 $d$ 互素。
对于每一个固定的因数 $d$，以 $d$ 为分母的最简分数有几个？显然，分子 $k$ 必须满足 $1 \le k \le d$ 且 $\gcd(k, d) = 1$，这样的 $k$ 恰好有 $\varphi(d)$ 个。
因为所有最简分数加起来总共还是最初的 $n$ 个分数，所以所有 $\varphi(d)$ 的总和等于 $n$。证明完毕。

根据算术基本定理，任何正整数 $n$ 都可以唯一分解为素数幂的乘积。我们设：

$n = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$

那么欧拉函数可以展开为：

$\varphi(n) = p_1^{a_1-1}(p_1 - 1) p_2^{a_2-1}(p_2 - 1) \dots p_m^{a_m-1}(p_m - 1)$

证明展开公式：

第一步：计算单一素数幂的欧拉函数 $\varphi(p^a)$
我们先不看复杂的 $n$，只看 $n$ 是一个素数的幂次的情况，即 $n = p^a$（$p$ 为素数，$a \ge 1$）。
欧拉函数 $\varphi(p^a)$ 的定义是：在 $1$ 到 $p^a$ 的正整数中，有多少个数与 $p^a$ 互素？
正难则反，我们可以用排除法：

1. $1$ 到 $p^a$ 之间总共有 $p^a$ 个数。
2. 因为 $p$ 是素数，一个数如果与 $p^a$ 不互素，那么它必定含有因子 $p$，也就是说，它必定是 $p$ 的倍数。
3. 在 $1$ 到 $p^a$ 中，$p$ 的倍数有哪些呢？
   有：$1 \cdot p, 2 \cdot p, 3 \cdot p, \dots, (p^{a-1}) \cdot p$。
   很显然，这样的数总共有 $p^{a-1}$ 个。我们把这些“不互素”的数从总数里踢出去，剩下的就是互素的数：
   $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p - 1)$

这也就是展开公式里那些 $p_i^{a_i-1}(p_i - 1)$ 碎片的来源。

第二步：拼装最终公式
有了第一步（素数幂的求法）和欧拉函数的积性公式 $\varphi(mn) = \varphi(m) \cdot \varphi(n)$，就可以得到最终的展开式了。
把任意正整数 $n$ 分解为不同素数幂的乘积：

$n = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$

因为底数是不同的素数，所以这些素数幂之间两两互素（即 $\gcd(p_i^{a_i}, p_j^{a_j}) = 1$）。我们连续使用“积性”公式拆开它们：

$\varphi(n) = \varphi(p_1^{a_1}) \cdot \varphi(p_2^{a_2}) \dots \varphi(p_m^{a_m})$

最后，把第一步得到的单一素数幂公式 $\varphi(p^a) = p^{a-1}(p - 1)$ 代入上面每一个括号里，就得到了最终的展开公式：

$\varphi(n) = p_1^{a_1-1}(p_1 - 1) p_2^{a_2-1}(p_2 - 1) \dots p_m^{a_m-1}(p_m - 1)$