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

此页面提供了涉及欧拉函数 $\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}}$ 并且我们已经证实了这一论点。