欧拉函数和证明

2019-08-16 / Math

 

证: 设 $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$