|
|
higher math online
定义 $G_e = \{x: 0\le x < n \land (x,n)=e\}$ 和 $R_d=\{y:0\le y < d \land (y,d)=1\}$。
如果 $n=de$，那么 $G_e$ 和 $R_d$ 有相同数量的元素。实际上，通过将 $R_d$ 的每个元素乘以 $e$，可以得到两个集合之间的一一对应关系。因此，$G_e$ 中有 $ϕ(d)$ 个元素。
证明 注意到 $0\le y < d ⇔ 0\le ey < ed ⇔ 0\le ey < n$，并且 $(y,d)=1 ⇔ (ey,ed)=e ⇔ (ey,n)=e$。这些事实表明 $y \in R_d ⇔ ey \in G_e。\quad\blacksquare$
假设 $n$ 是一个正整数。那么 $n=\sum_{0 < d \vert n} \phi(d)$。
证明 由于从 0 到 $n-1$ 的每个数正好在一个 $G_e$ 中，因此 $n=\sum_{0 < e \vert n}|G_e|=\sum_{0 < e \vert n}\phi(d)=\sum_{0 < d \vert n}\phi(d)$。最后一个等式是有效的，因为当 $e$ 遍历 $n$ 的正因子时，$d$ 也遍历 $n$ 的正因子，即两个和实际上是相同的，只是它们以相反的顺序加起来。$\quad\blacksquare$
例子 如果 $n=20$，$\phi(1)+\phi(2)+\phi(4)+\phi(5)+\phi(10)+\phi(20)=1+1+2+4+4+8=20$。
如果 $n=33$，$\phi(1)+\phi(3)+\phi(11)+\phi(33)=1+2+10+20=33$。 |
|
