欧拉函数$phi(n)$表示不超过$n$的正整数中与$n$互质的个数，并且有：
$\varphi(n)= n\sum\limits_{p|n}(1-{\frac 1{p}})$
显然有若$n$素数：
$\varphi(n)=n-1$
并且考虑$mp$，若$p$为素数，则对任意整数$k$：
$(mp, k)\Leftrightarrow (m, k)$
于是在每个模$p$的剩余系中有$\varphi(m)$个数与$mp$互质，因此：
$\varphi(mp)=\varphi(m)\varphi(p)=\varphi(m)(p-1)$
原文：http://www.cnblogs.com/astoninfer/p/5697402.html