Euler 函数

在数论中, Euler 函数 $\phi (n)$ 表示大小不超过 $n$ 且与 $n$ 互素的正整数个数.

1定义

定义 1.1. Euler 函数是函数$$\phi :{\mathbb{N}}_{+}\to \mathbb{N},\phi (n)=1,2,\dots ,n中与n互素的正整数个数.$$

2性质

基本性质

参见: Möbius 函数 (数论)

利用 Möbius 反演, 可知:

$$\begin{array}{rl}\phi (n)& =\sum _{\begin{array}{c}k\le n\\ (k,n)=1\end{array}}1=\sum _{k\le n}\sum _{d|(k,n)}\mu (d)\\ & =\sum _{d|n}\mu (d)\sum _{\begin{array}{c}k\le n\\ d|k\end{array}}1=\sum _{d|n}\mu (d)\frac{n}{d}\end{array}$$

将此与 Dirichlet 卷积的性质结合, 我们就可以得到 Euler 函数的若干基本性质:

命题 2.1. Euler 函数是积性函数, 即 $a,b$ 互素时 $\phi (ab)=\phi (a)\phi (b)$

命题 2.2. $$\phi (n)=n\prod _{p|n}\left(1-\frac{1}{p}\right)$$

命题 2.3. $$\sum _{d|n}\phi (d)=n$$

Euler 定理

定理 2.4 (Euler). 当 $(a,q)=1$ 时总有 $a^{\phi (q)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}q)$

证明. 用 $a_1,a_2,\dots ,a_{\phi (q)}$ 表示模 $q$ 缩剩余系 ${\mathbb{Z}}_q^{\times }$ 中的所有元素. 则利用 ${\mathbb{Z}}_q^{\times }$ 的乘法封闭性可知对于任意 $a\in {\mathbb{Z}}_q^{\times }$ 总有: $$\prod _{1\le i\le \phi (q)}(a_{i}a)\equiv \prod _{1\le i\le \phi (q)}{a}_i(\mathrm{m}\mathrm{o}\mathrm{d}q)$$再利用消去律, 即得: $$a^{\phi (q)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}q)$$

$\square$

渐近性质

最大阶与最小阶

由于 $\phi (n)\le n-1$ 且对于所有素数 $p$ 均有 $\phi (p)=p-1$. 而因为素数有无穷个, 所以 $n$ 就是 $\phi (n)$ 的最大阶:

命题 2.5 (Euler 函数的最大阶). $$\underset{n\to \infty }{\mathrm{limsup}}\frac{\phi (n)}{n}=1$$

另外一方面, 当 $1\le t\le n$ 时利用命题 2.2 可知:

$$\frac{\phi (n)}{n}\ge \prod _{p\le t}\left(1-\frac{1}{p}\right)\prod _{\begin{array}{c}p|n\\ p>t\end{array}}\left(1-\frac{1}{p}\right)$$

利用 Mertens 定理可知:

$$\prod _{p\le t}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma }}{\log t}+O\left(\frac{1}{{\log }^{2}t}\right)$$

很明显 $n$ 中 $>t$ 的素因子个数不超过 $\log n/\log t$, 所以有:

$$\begin{array}{rl}\frac{\phi (n)}{n}& >\frac{e^{-\gamma }}{\log t}{\left(1-\frac{1}{t}\right)}^{\log n/\log t}\left\{1+O\left(\frac{1}{\log t}\right)\right\}\\ & =\frac{e^{-\gamma }}{\log t}\left\{1+O\left(\frac{\log n}{t\log t}\right)\right\}\left\{1+O\left(\frac{1}{\log t}\right)\right\}\end{array}$$

现代入 $t=\log n$, 即得:

$$\phi (n)>\frac{e^{-\gamma }n}{\log \log n}\left\{1+O\left(\frac{1}{\log \log n}\right)\right\}$$(1)

另一方面当 $n_x$ 表示大小不超过 $x$ 的素数乘积时, 有:

$$\phi (n_x)=n_x\prod _{p\le x}\left(1-\frac{1}{p}\right)\sim \frac{e^{-\gamma }n}{\log x}$$

然而根据素数定理可知:

$$\log n_x=\sum _{p\le x}\log p=\vartheta (x)\sim x$$

所以有:

$$\phi (n_x)\sim \frac{e^{-\gamma }{n}_x}{\log \log n_x}$$(2)

现在将 (1) 和 (2) 相结合, 可知 $\phi (n)$ 的最小阶为 $e^{-\gamma }n/\log \log n$:

命题 2.6 (Euler 函数的最小阶). $$\underset{n\to \infty }{\mathrm{liminf}}\frac{\phi (n)\log \log n}{n}=e^{-\gamma }$$

平均阶

利用 $\phi (n)$ 的定义, 可知:

$$\begin{array}{rl}\sum _{n\le x}\phi (n)& =\sum _{n\le x}\sum _{n=ab}\mu (a)b=\sum _{a\le x}\mu (a)\sum _{b\le x/a}b\\ & =\sum _{a\le x}\mu (a)\left\{\frac{x^2}{2a^2}+O\left(\frac{x}{a}\right)\right\}\\ & =\frac{x^2}{2}\sum _{a\le x}\frac{\mu (a)}{a^2}+O\left\{x\sum _{a\le x}\frac{1}{a}\right\}\end{array}$$

利用 Dirichlet 级数的 Euler 乘积可知:

$$\sum _{a\ge 1}\frac{\mu (a)}{a^2}=\prod _p\left(1-\frac{1}{p^2}\right)=\frac{1}{\zeta (2)}$$

再根据常用结论 ${\sum }_{a>x}1/a^2=O(1/x)$ 以及 ${\sum }_{a\le x}1/a=O(\log x)$, 我们就得到了结论:

命题 2.7 (Euler 函数的平均阶). $$\sum _{n\le x}\phi (n)=\frac{x^2}{2\zeta (2)}+O(x\log x)$$换言之, $\phi (n)$ 的均阶为 $n/\zeta (2)$.

倒数和

在本节中, 我们将证明:

定理 2.8 (Landau). 存在常数 $A,B$ 使得: $$\sum _{n\le x}\frac{1}{\phi (n)}=A(\log x+B)+O\left(\frac{\log x}{x}\right)$$其中: $$A=\frac{\zeta (2)\zeta (3)}{\zeta (6)}=\frac{315\zeta (3)}{2{\pi }^4}$$$$B=\gamma -\sum _p\frac{\log p}{p^2-p+1}$$

利用命题 2.2, 可知:

$$\frac{1}{\phi (n)}=\frac{1}{n}\prod _{p|n}\left(1+\frac{1}{p-1}\right)=\frac{1}{n}\sum _{d|n}\frac{{\mu }^2(d)}{\phi (d)}$$

因此有:

$$\begin{array}{rl}\sum _{n\le x}\frac{1}{\phi (n)}& =\sum _{n\le x}\frac{1}{n}\sum _{n=ab}\frac{{\mu }^2(a)}{\phi (a)}=\sum _{a\le x}\frac{{\mu }^2(a)}{a\phi (a)}\sum _{b\le x/a}\frac{1}{b}\\ & =\sum _{a\le x}\frac{{\mu }^2(a)}{a\phi (a)}\left\{\log \frac{x}{a}+\gamma +O\left(\frac{a}{x}\right)\right\}\\ & =(\log x+\gamma )\sum _{a\le x}\frac{{\mu }^2(a)}{a\phi (a)}+\sum _{a\le x}\frac{{\mu }^2(a)}{a\phi (a)}(-\log a)\\ & +O\left\{\frac{1}{x}\sum _{a\le x}\frac{{\mu }^2(a)}{\phi (a)}\right\}\end{array}$$

当 $F(s)$ 表示 ${\mu }^2(n)/\phi (n)$ 的 Dirichlet 级数时, 根据 Euler 乘积可知:

$$F(s)=\sum _{a\ge 1}\frac{{\mu }^2(a)}{a^s\phi (a)}=\prod _p\left(1+\frac{p^{-s}}{p-1}\right)=\prod _p\frac{p^{-s}+p-1}{p-1}$$(3)

这意味着:

$$\begin{array}{rl}F(1)& =\prod _p\frac{p^{-2}-p^{-1}+1}{1-p^{-1}}=\prod _p\frac{1+p^{-3}}{1-p^{-2}}\\ & =\prod _p\frac{1-p^{-6}}{(1-p^{-2})(1-p^{-3})}=\frac{\zeta (2)\zeta (3)}{\zeta (6)}=A\end{array}$$

另一方面通过对 (3) 取对数导可得:

$$\begin{array}{rl}\frac{F^{\prime }}{F}(s)& =\frac{\mathrm{d}}{\mathrm{d}s}\log F(s)=\sum _p\frac{\mathrm{d}}{\mathrm{d}s}\log \frac{p^{-s}+p-1}{p-1}\\ & =\sum _p\frac{-p^{-s}\log p}{p^{-s}+p-1}=-\sum _p\frac{\log p}{p^{s+1}-p^s+1}\end{array}$$

因此有:

$$F^{\prime }(1)=F(1)\frac{F^{\prime }}{F}(1)=A(B-\gamma )$$

另一方面由于:

$$\begin{array}{rl}{S}_1(x)& =\sum _{a\le x}\frac{{\mu }^2(a)}{\phi (a)}\le \sum _{\begin{array}{c}p|a\Rightarrow p\le x\end{array}}\frac{{\mu }^2(a)}{\phi (q)}\\ & =\prod _{p\le x}\left(1+\frac{1}{p-1}\right)=\prod _{p\le x}{\left(1-\frac{1}{p}\right)}^{-1}=O(\log x)\end{array}$$

所以利用分部求和法, 可知:

$$\begin{array}{rl}{S}_2(x)& =\sum _{a>x}\frac{{\mu }^2(a)}{a\phi (a)}=\frac{S_1(x)}{x}+{\int }_x^{\infty }\frac{S_1(t)}{t^2}\mathrm{d}t\\ & \ll \frac{\log x}{x}+{\int }_x^{\infty }\frac{\log t}{t^2}\mathrm{d}t=O\left(\frac{\log x}{x}\right)\end{array}$$

同样地, 有:

$$\begin{array}{rl}{S}_3(x)& =\sum _{a>x}\frac{{\mu }^2(a)}{a\phi (a)}\log a=-{\int }_x^{\infty }\log t\mathrm{d}{S}_2(t)\\ & =S_2(x)\log x+{\int }_x^{\infty }\frac{S_2(t)}{t}\mathrm{d}t\\ & =S_2(x)\log x+O\left(\frac{\log x}{x}\right)\end{array}$$

综上所述, 可知:

$$\begin{array}{rl}\sum _{n\le x}\frac{1}{\phi (n)}& =[F(1)-S_2(x)](\log x+\gamma )+F^{\prime }(1)+S_3(x)+O\left(\frac{S_1(x)}{x}\right)\\ & =A(\log x+B)-S_2(x)\log x+S_3(x)+O\left(\frac{\log x}{x}\right)\\ & =A(\log x+B)+O\left(\frac{\log x}{x}\right)\end{array}$$

至此定理 2.8 证明完毕.

术语翻译

Euler 函数 • 英文 Euler’s totient function • 德文 eulersche $\phi$-Funktion • 法文 indicatrice d’Euler