定义
$\varphi(n)$：$1$到$n$中与$n$互质的数的个数
$$
\varphi(n)=n\prod_{p|n}(1-{1\over p})
$$
其中$p$是$n$的素因子
证明
关于这个公式的理解，可以先考虑只有一个素数因子的形式。
若$n=a^p$,则$[1,n]$中能被a整除的数分别为$a,2a,3a,…,a^{p-1}a$，共$a^{p-1}={n\over a}$个，剩下的是不能被$a$整除的数，自然的就和n互质。因此容易得到$\varphi(n)=n−{n\over a}=n(1−{1\over a})$
从上面的例子可以看出，a的倍数其实是在$[1,x]$之间平均分布的。这样的平均分布适用于任何的数的倍数。
当一个数有多个素数因子的时候，可以利用这些因子的倍数是各自平均分布的性质，依次累乘上$(1−{1\over p})$.相当于筛去了$p$的倍数。
举个例子：$30=2·3·5$
$1,2,3,4,5,6,7,8,9,10,……,28,29,30$
共30个数，先乘$(1−{1\over 2})$剩下了15个数：
$1,3,5,7,9,11,13,15,17,19,21,23,25,27,29$
再乘$(1−{1\over 3})$筛去了5个，剩下10个数：
1,5,7,11,13,17,19,23,25,29
再乘$(1−{1\over 5})$筛去2个，剩下8个数：
1,7,11,13,17,19,23,29
这是因为被筛去的数是平均分布的，则剩下的数中，为另一个素数的倍数也是平均分布的。