数论 · 欧拉反演

· · 个人记录

前言

小性质，QWQ。

定理

即 $$\sum_{d|n}\varphi(d) = n$$ ## 证明 通过积性函数证明。 将所有因子的欧拉函数之和记为 $σ(n)$。 ### 1 证明它是积性函数。 设 $m\perp n$，即它们的公因子为 1。 因为 $\varphi$ 为积性函数，所以有： $$ σ(n)* σ(m) = \sum_{p|n}\varphi(p)* \sum_{q|m} \varphi(q) = \sum_{p|n}\sum_{q|m} \varphi(p)* \varphi(q)=\sum_{p|n}\sum_{q|m} \varphi(pq) $$ 因为所有 $pq$ 之和就是 $nm$ 的因子之和，所以： $$ σ(n)* σ(m)=σ(nm) $$ ### 2 对于 $m=p^k$，$p$ 为素数时，根据欧拉函数的性质，有： $$ σ(m)=\sum_{i=0}^k \varphi(p_i) =1+(p - 1) +(p^2 - p)+\cdots +(p^k - p^{k-1})=p^k = m $$ 注：当 $m$ 为素数时即 $k$ 的值为 1 的情况。 ________________ ____________________ $\varphi(p^k)=p^k - p^{k-1}$ 的补充证明。 证明： 一共有 $p_k$ 个数。 而与 $p_k$ 不互质的数只有 $p$ 的正整数倍数，而它们又是均匀分布的，所以个数为：$p^k \div p = p^{k - 1}$。 所以答案即为所有数个数减去与 $p^k$ 不互质的数个数，即： $$ \varphi(p^k)=p^k - p^{k-1} $$ 证毕。 -------------------- ---------------- ### 3 综上，可得出： $$ σ(n)=\sum σ(p_i^{k_i}) = \sum p_i^{k_i} = n $$ 证毕。 _____________ ——$End$——