欧拉函数和证明

 

证： 设 $n$ 为正整数，则：$\sum_{d|n}\varphi(d) = n$

证明： 考虑有理数集

$S = {\frac{r}{n}|r=1,2,\dots,n}$

将 $S$ 中的每个数化为既约分数，得：

$S^* = {\frac{r/(r,n)}{n/(r,n)} = \frac{h}{k}|r=1,2,\dots,n}$

显然，$S^*$ 中的 $n$ 个分数值仍然各不相同。

$S^*$ 中的 $\frac{h}{k}$ 是既约分数，则有：

$k|n, (h,k) = 1, h \leq k$

反之，对于给定的 $n$ ，任一满足上述条件的分数 $\frac{h}{k}$ 在 $S^*$ 中。这是因为：

$\frac{h \times \frac{n}{k}}{k \times \frac{n}{k}} = \frac{r}{n}, r \leq n$

进一步，对于每个 $k|n$ ，满足时该条件的分数 $\frac{h}{k}$ 有 $\varphi{k}$ 个（因为与 $k$ 互素的 $h$ 值有 $\varphi{k}$ 个）。

所以满足该条件的分数 $\frac{h}{k}$ 共有 $\sum_{d|n} \varphi{(d)}$ 个。

而 $S^*$ 中有 $n$ 个分数，故：$\sum_{d|n}\varphi(d) = n$