欧拉函数公式证明2（ACCEPTED）

· · 算法·理论

对于一个质数 p 来讲，显然

；

对于一个数 p^q，其中 p 为质数且 q\in N_+ 来讲，在 1 ~ p^q 中与 p 成倍数的数的个数为 p^{q-1},所以

；

对于两个质数的积 m\cdot n 来讲，在 [1,m\cdot n] 中，有 n 个 m 的倍数，有 m 个 n 的倍数，有一个 m\cdot n 的倍数，则

由（A）可知

；

对于一个数 p_1\cdot p_2\cdot p_3(p_i为质数) 来讲，有 p_2\cdot p_3 个 p_1 的倍数，剩下有 p_1\cdot p_3-\frac{p_1\cdot p_2\cdot p_3}{p_1\cdot p_2}=(p_1-1)\cdot p_3 【由（C）得来】个 p_2 的倍数，剩下有 (p_1-1)\cdot (p_2-1)\cdot p_3 个 p_3 的倍数，所以

\phi (p_1\cdot p_2\cdot p_3)=p_1\cdot p_2\cdot p_3-p_2\cdot p_3-(p_1-1)\cdot p_3-(p_1-1)\cdot (p_2-1)\cdot p_3 \varphi (p_1\cdot p_2\cdot p_3)=(p_1-1)\cdot (p_2-1)\cdot (p_3-1)

显然，这也可由（C）得来；

对于一个数 m=\prod\limits_{1 \leq j \leq n}^{n} p_j^{\alpha_j}（{ p_n }，{ \alpha_n }， m \in N_+）来讲，

\varphi(m)={p_1}^{q_1-1}\cdot (p_1-1)\cdot{p_2}^{q_2-1}\cdot (p_2-1) ……{p_n}^{q_n-1}\cdot (p_n-1) \because m=\prod\limits_{1 \leq j \leq n}^{n} p_j^{\alpha_j}=p_1^{\alpha_1}\cdot p_2 ^{\alpha_2}……p_n^{\alpha_n} \therefore \varphi(m)=m\cdot \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}……\frac{p_n-1}{p_n}

那么 \varphi(m)= m \cdot \prod\limits_{1\leq j \leq n}^{n}{(1-\frac{1}{p_j})} .