作业十：Prove the following therem.

Therem:

Let $m=p_1^{a_1}p_2^{a_2}......p_k^{a_k}$
$ψ(m)=m(1-1/p_1)(1-p_2)......(1-p_k)$

计算机数学

---

证明如下：

根据题意要求：
$p_1--p_k必为素数，否则，ψ(m)无法展开计算$

所以，由已知被证定理得：
m,n互质时，即$gcd(m,n)=1$ 有$ψ(m^in^j)=ψ(m^i)ψ(n^j)$
所以得$ψ(m)=ψ(p_1^{a_1})...ψ(p_k^{a_k})$
由计算方法：$ψ(p^k)=p^k-p^{k-1}(p是素数)得$

$$\begin{align} ψ(m)&=ψ(p_1^{a_1})...ψ(p_k^{a_k})\\ &=(p_1^{a1}-p_1^{a_1-1})...(p_k^{a_k}-p_k^{a_2-1})\\ &=p_1^{a_1-1}...p_k^{a_k-1}(p_1-1)...(p_k-1)\\ &=p_1^{a_1}...p_k^{a_k}(p_1-1)...(p_k-1)/p_1...p_k\\ &=m(p_1-1)/p_1......(p_k-1)/p_k\\ &=m(1-1/p_1)...(1-1/p_k)\\ \end{align}$$
证毕