数学/数论/欧拉函数的著名定理

此页面提供了涉及欧拉函数$\varphi (k)$和莫比乌斯函数$\mu (k)$的恒等式的证明。

与n互质且小于等于n的整数之和

恒等式的证明

$\sum _{1\leq k\leq n \atop (k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 2$

利用以下事实

$(k,n)=d\quad \Leftrightarrow \quad (n-k,n)=d$

因为如果$d|n$和$d|k$则$d|n-k$，如果$d|n$和$d|(n-k)$则$d|n-(n-k)=k.$

这意味着对于$n>2$，我们可以将与n互质的k分组为对

$(k,n-k)\quad {\mbox{ where }}\quad k<n-k.$.

情况$k=n/2$不会出现，因为当n为奇数时$n/2$不是整数，当n为偶数时，我们有$(n/2,n)=n/2>1$，因为我们假设$n>2.$有

${\frac {\varphi (n)}{2}}$

对，每对的元素之和为

$k\;+\;n-k\;=n,$

因此

$\sum _{(k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 3.$

情况 $n=2$ 可以通过直接代入验证，也可以包含在公式中。

涉及取整函数的欧拉函数恒等式的证明

恒等式的证明

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor$

是用数学归纳法对 $n$ 证明的。基本情况是 $n=1$，我们可以看到结论成立

$\varphi (1)/1=1={\frac {\mu (1)}{1}}\left\lfloor 1\right\rfloor .$

为了归纳步骤，我们需要证明

${\frac {\varphi (n+1)}{n+1}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \right)+{\frac {\mu (n+1)}{n+1}}.$

关键观察是

$\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \;=\;{\begin{cases}1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise, }}\end{cases}}$

因此，这个和是

$\sum _{k|n+1,\;k<n+1}{\frac {\mu (k)}{k}}+{\frac {\mu (n+1)}{n+1}}=\sum _{k|n+1}{\frac {\mu (k)}{k}}.$

现在，事实是

$\sum _{k|n+1}{\frac {\mu (k)}{k}}={\frac {\varphi (n+1)}{n+1}}$

是一个基本的totient恒等式。要看到它成立，设 $p_{1}^{v_{1}}p_{2}^{v_{2}}\ldots p_{q}^{v_{q}}$ 是 n+1 的素数分解。那么

${\frac {\varphi (n+1)}{n+1}}=\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}}}\right)=\sum _{k|n+1}{\frac {\mu (k)}{k}}$

根据 $\mu (k).$ 的定义。这结束了证明。

另一种证明方法是将 ${\frac {\varphi (k)}{k}}=\sum _{d|k}{\frac {\mu (d)}{d}}$ 直接代入恒等式的左侧，得到 $\sum _{k=1}^{n}\sum _{d|k}{\frac {\mu (d)}{d}}.$

现在我们问项 ${\begin{matrix}{\frac {\mu (d)}{d}}\end{matrix}}$ 在二重和中出现了多少次。答案是，它对于 $d$ 的每个倍数 $k$ 都会出现，但恰好有 ${\begin{matrix}\left\lfloor {\frac {n}{d}}\right\rfloor \end{matrix}}$ 个这样的倍数，这意味着该和为

$\sum _{d=1}^{n}{\frac {\mu (d)}{d}}\left\lfloor {\frac {n}{d}}\right\rfloor$

如前所述。

---

过滤掉 ${\begin{matrix}\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \end{matrix}}$ 的零值也可以用来证明恒等式

$\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right).$

基本情况是 $n=1$，我们有

$\varphi (1)=1={\frac {1}{2}}\left(1+\mu (1)\left\lfloor {\frac {1}{1}}\right\rfloor ^{2}\right)$

它成立。归纳步骤要求我们证明

$\varphi (n+1)={\frac {1}{2}}\sum _{k=1}^{n}\mu (k)\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)\;+\;{\frac {1}{2}}\;\mu (n+1)\;\left\lfloor {\frac {n+1}{n+1}}\right\rfloor ^{2}.$

接下来观察

$\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\;=\;{\begin{cases}2{\frac {n+1}{k}}-1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise.}}\end{cases}}$

这给出了和的以下结果

${\frac {1}{2}}\sum _{k|n+1,\;k<n+1}\mu (k)\left(2{\frac {n+1}{k}}-1\right)\;+\;{\frac {1}{2}}\;\mu (n+1)={\frac {1}{2}}\sum _{k|n+1}\mu (k)\left(2\;{\frac {n+1}{k}}-1\right).$

分别处理两个内部项，我们得到

$(n+1)\sum _{k|n+1}{\frac {\mu (k)}{k}}-{\frac {1}{2}}\sum _{k|n+1}\mu (k).$

这两个中的第一个精确地是 $\varphi (n+1)$，正如我们之前所见，第二个是零，这是根据莫比乌斯函数的基本性质（使用与上面相同的 $n+1$ 因式分解，我们有 ${\begin{matrix}\sum _{k|n+1}\mu (k)=\prod _{l=1}^{q}(1-1)=0\end{matrix}}$。）这完成了证明。

这个结果也可以用容斥原理来证明。将等式改写为

$-1+2\sum _{k=1}^{n}\varphi (k)=\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}.$

现在我们看到，等式的左边表示 [1,n] × [1,n] 中的格点 (a, b) 的数量，其中 a 和 b 互质。使用集合 $A_{p}$，其中 p 是小于或等于 n 的素数，表示两个坐标都可被 p 整除的点的集合，我们有

$\left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.$

这个公式计算了 a 和 b 不互质的点的对数。基数如下

$\left|A_{p}\right|=\left\lfloor {\frac {n}{p}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\right|=\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2},\;\ldots$

符号是 ${\begin{matrix}-\mu (pqr\cdots )\end{matrix}}$，因此具有互质坐标的点的数量为

$\mu (1)\,n^{2}\;+\;\sum _{p}\mu (p)\left\lfloor {\frac {n}{p}}\right\rfloor ^{2}\;+\;\sum _{p<q}\mu (pq)\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2}\;+\;\sum _{p<q<r}\mu (pqr)\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2}\;+\;\cdots$

但这正是$\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}$，因此我们得到了结论。

欧拉函数的平均阶

我们将使用上一节的最后一个公式来证明以下结果

${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)$

利用$x-1<\lfloor x\rfloor \leq x$，我们得到上限

${\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k){\frac {n^{2}}{k^{2}}}\right)={\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}$

以及下限

${\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k)\left({\frac {n^{2}}{k^{2}}}-2{\frac {n}{k}}+1\right)\right)$

即

${\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}+{\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)$

处理最后两项并利用第n个调和数的渐近展开，我们有

$-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}>-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {1}{k}}=-{\frac {1}{n}}H_{n}>-{\frac {1}{n}}(\log n+1)$

以及

${\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)>-{\frac {1}{2n}}.$

现在我们检查上下界中各项的阶数。 项 ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$ 是 ${\mathcal {O}}(1)$，与 $\zeta (2)$ 作比较可知，其中 $\zeta (s)$ 是黎曼ζ函数。 下一个最大项是下界中的对数项。

到目前为止，我们已经证明了

${\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)$

现在需要渐进地评估 ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$，我们已经看到它收敛。 黎曼ζ函数的欧拉乘积为

$\zeta (s)=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)^{-1}{\mbox{ for }}\Re (s)>1.$

从莫比乌斯函数的定义可以立即得到

${\frac {1}{\zeta (s)}}=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}.$

这意味着

${\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}={\frac {1}{2}}{\frac {1}{\zeta (2)}}+{\mathcal {O}}\left({\frac {1}{n}}\right)$

其中积分${\begin{matrix}\int _{n+1}^{\infty }{\frac {1}{t^{2}}}dt\end{matrix}}$ 用于估计${\begin{matrix}\sum _{k>n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}.$ 但${\begin{matrix}{\frac {1}{2}}{\frac {1}{\zeta (2)}}={\frac {3}{\pi ^{2}}}\end{matrix}}$ 并且我们已经证实了这一论点。

φ(n)/n 的平均阶

上一节的内容，加上恒等式

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor$

也为以下证明提供了依据

${\frac {1}{n}}\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}={\frac {6}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right).$

和之前一样，我们得到一个上限

${\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}{\frac {n}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}$

以及下限

$-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}+\sum _{k=1}^{n+1}{\frac {\mu (k)}{k^{2}}}.$

现在应用上一节的估计得到结果。

不等式

首先，我们证明

$\lim \inf {\frac {\varphi (n)}{n}}=0{\mbox{ and }}\lim \sup {\frac {\varphi (n)}{n}}=1.$

当 n 是素数 p 的幂时，后一个式子成立，因为有

${\frac {\varphi (n)}{n}}=1-{\frac {1}{p}},$

当 *p* 足够大时，这个值会任意接近 1（由于素数有无穷多个，所以我们可以取任意大的 *p*）。

为了看到前者，令 *n*_*k* 为前 *k* 个素数的乘积，记为 $p_{1},p_{2},...,p_{k}$。令

$r_{k}={\frac {\varphi (n_{k})}{n_{k}}}=\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).$

那么

${\frac {1}{r_{k}}}=\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right)^{-1}>\sum _{m=1}^{p_{k}}{\frac {1}{m}}=H_{p_{k}},$

一个调和数。因此，根据著名的界限 $H_{n}>\log n$，我们有

${\frac {1}{r_{k}}}>\log p_{k}.$

由于对数是无界的，取任意大的 *k* 可以确保 *r*_*k* 取得任意接近于零的值。

我们使用与第一部分相同的 *n* 因式分解来证明

${\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}$.

注意

$\varphi (n)\sigma (n)=n\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}}}\right)\prod _{l=1}^{q}{\frac {p_{l}^{v_{l}+1}-1}{p_{l}-1}}=n\prod _{l=1}^{q}{\frac {p_{l}-1}{p_{l}}}\;{\frac {p_{l}^{v_{l}+1}-1}{p_{l}-1}}$

即

$n\prod _{l=1}^{q}\left(p_{l}^{v_{l}}-{\frac {1}{p_{l}}}\right)=n^{2}\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right).$

由于

$\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right)<1.$

当n为素数时，我们任意接近这个界限。对于下界，请注意

$\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{v_{l}+1}}}\right)\geq \prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}^{2}}}\right)>\prod _{p}\left(1-{\frac {1}{p^{2}}}\right),$

其中乘积是对所有素数进行的。我们已经见过这个乘积，如

$\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}$

因此

$\prod _{p}\left(1-{\frac {1}{p^{2}}}\right)={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}$

我们有这个结论。最接近这个界限的n值是前k个素数的乘积。

外部链接

• Chris K. Caldwell，gcd(n,m)=1 的概率是多少？
• Bordellès, Olivier, 在$[1,n]$ 中与q互素的数