假设一个数 \(N =\) \(p_{1}^{c_{1}} \times p_{2}^{c_{2}} \times p_{3}^{c_{3}}\) … $ \times p_{m}^{c_{m}}$ 。 \(p_{1}\)，\(p_{2}\)，\(p_{3}\) …\(p_{m}\) 为 \(N\) 的质因子。
\(\varphi(n)\) = $N \times \frac{P_{1}-1}{P_{1}} \times \frac{P_{2}-1}{P_{2}} \times \frac{P_{3}-1}{P_{3}} $ … $ \times \frac{P_{m}-1}{P_{m}}$
然后就是为什么？？？
设 \(N\) 的质因子只有 \(P_{1}\) 和 \(P_{2}\) （举简单点的例子）。
众所周知，满足条件的数量=总数量-不满足条件的数量
总数量已经知道是 \(N\) 个(1~N),所以先看不满足条件的数量。不满足条件的数量就是不与 \(N\) 互质的数的数量。则是 \(P_{1}\) 的倍数的数量和 \(P_{2}\) 的倍数的数量。
\(P_{1}\) 的倍数的数量就是 \(\frac{N}{P_{1}}\) ， \(P_{2}\) 的倍数的数量就是 \(\frac{N}{P_{2}}\) 。
然后合法的就等于 \(N - \frac{N}{P_{1}} - \frac{N}{P_{2}}\)
这对吗？？？
显然，我们多减了一次重复值 \(P_{1}P_{2}\) 的倍数的数量。所以加上：
\(\varphi(N) = N - \frac{N}{P_{1}} - \frac{N}{P_{2}} + \frac{N}{P_{1} P_{2}}\)
继续转换，发现公式里都有一个 \(N\) ，把 \(N\) 提出来：
\(\varphi(N) = N \times ( 1 - \frac{1}{P_{1}} - \frac{1}{P_{2}} + \frac{1}{P_{1} P_{2}})\)
最后，根据公式 $ (a-b) \times (a-c) = a^2 - ab -ac +bc$ 得到：
$\varphi(N) = N \times ( 1 - \frac{1}{P_{1}}) \times ( 1 - \frac{1}{P_{2}} ) $