Euler 函数

在数论中，Euler 函数是一个常见的数论函数，一个正整数的 Euler 函数值是与该正整数互素的比该正整数小的所有非负整数的个数。

概念

设有正整数$n \in \mathbb{N}^+$，那么$\varphi(n)$表示$0,1,\cdots,n-1$当中与$n$互素的整数的个数。

性质

1. $\varphi(n)$是积性数论函数，但它不是完全积性的：当$(m, n) > 1$时$\varphi(mn) > \varphi(m) \varphi(n).$
2. 设有标准分解式$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$，那么
   $$\varphi (n)=\prod _{i=1}^{k}(p_{i}^{\alpha _{i}}-p_{i}^{\alpha _{i}-1})=n\prod _{i=1}^{k}\left(1-{\dfrac {1}{p_{i}}}\right).$$
3. 设$d$是正整数$n$的正因子，且$d \ne n$，那么$n - \varphi(n) > d - \varphi(d).$
4. 对于任意正整数$d > 2$，存在无穷多个正整数$n$使得$d \nmid \varphi(n).$
5. 若$n > 1, \varphi(m) = \varphi(mn), \forall m \in \N^+$，则必有$n = 2, 2 \nmid m.$
6. 当$n \geqslant 2$时，$\varphi(n) = \dfrac{2}{n} \sum_{\overset{i=1}{\underset{(i,n)=1}{}}}^n i.$
7. （卷积性质）$\sum_{d:d|n} \varphi(d) = n, \sum_{d:d|n} \dfrac{\mu(d)}{d} = \dfrac{\varphi(n)}{n}.$
8. $\varphi(n) = \sum_{k=1}^n \prod_{p:p|n} \left( 1 - \dfrac{1}{p} \sum_{\alpha=1}^p \text{e}^{\frac{2\pi\text{i}l\alpha}{p}} \right)$

推广

设$k$是给定的正整数，$\varphi_k (n)$表示满足以下条件的数组的个数：

$1 \leqslant d_j \leqslant n, 1 \leqslant j \leqslant k \text{ and } (d_1, d_2, \cdots, d_k, n) = 1.$

那么有

1. $\sum_{d:d|n} \varphi_k (d) = n^k.$
2. $\varphi_k(n) = n^k \prod_{p:p|n} \left( 1 - \dfrac{1}{p^k} \right).$

均值问题

$$\sum_{n:n \leqslant x} \varphi(n) = \dfrac{1}{2} \left( \sum_{d=1}^\infty \dfrac{\mu(d)}{d^2} \right) x^2 + r_4(x), |r_4(x)| \leqslant 3x\ln x + 4x.$$

进一步

$$\left| \dfrac{1}{x} \sum_{n:n \leqslant x} \left( \varphi(n) - \dfrac{6n}{\pi^2} \right) \right| < 3\ln x + 5.$$

平均来看，$\varphi(n) \sim \dfrac{6n}{\pi^2}.$