欧拉函数 φ(n) 的几个常用性质

文章目录

• 当 x 为质数 p 的 k 次幂时
• 欧拉函数是积性函数
• 当 n 为奇数时
• p 整除 n/p 时
• φ(n)=φ(n/p)*(p-1)
• n 的所有因子欧拉函数之和为 n
• 参考

之前我们已经知道欧拉函数 $\varphi(n)$ 的计算公式：

\displaystyle \varphi (n)=n \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i})

我们还知道它的两条性质：
如果$\varphi(x)$中的x是质数 p 的 k 次幂，那么 $\displaystyle \varphi (x)=\varphi (p^k)=(p-1)p^{k-1}$ ；
欧拉函数是积性函数，如果 x 和 y 互质，则 $\varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1)$ 。

今天我们要证明上述性质，再介绍几条新的性质。

温馨提示：
本文中有大量 KaTeX 公式，请确保浏览器支持，否则卡到超乎你想象。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。

本文隶属⌈ 数论学习系列 ⌋。
本文是 欧拉函数、费马小定理与欧拉定理详解 一文的补充。建议先阅读后者。

当 x 为质数 p 的 k 次幂时

$\varphi(x)$ 中的 x 是质数 p 的 k 次幂时：

\displaystyle \varphi (x)=\varphi (p^k)=p^k-p^{k-1}=(p-1)p^{k-1}

证明：小于等于 $p^k$ 的正整数个数为 $p^k$ 个，
其中和 $p$ 不互质的正整数有：$1 \ast p, 2 \ast p, \dots ,r \ast p$。
显然可以得到：$r=\frac {p^k} {p}-1 = p^{k-1}$。剩下的就是与 $p$ 互质的。
那么就得到了：$\varphi (n)=p^k-p^{k-1}$。

欧拉函数是积性函数

\displaystyle \varphi(nm)=\varphi (n) \ast \varphi (m),(n,m)=1

证明：要证明这个公式，我们可以画张表：

\displaystyle
\begin{matrix}
1 & 2 & \cdots & r & \cdots & m \\
m+1 & m+2 & \cdots & m+r & \cdots & 2m \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
(n-t)m+1 & (n-t)m+2 & \cdots & (n-t)m+r & \cdots & (n-t+1)m \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
(n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \\
\end{matrix}

在这张表里，每行都是一个模 n 的完全剩余系，其中有 $\varphi(n)$ 个与 n 互质的数字；每列都是一个模 m 的完全剩余系，其中有 $\varphi (m)$ 个与 m 互质的数字。一个数字要和 nm 互质，那么它就要和 n 互质又和 m 互质。那么一共就有 $\varphi(n)\varphi(m)$ 个与 nm 互质的数字，也就是说 $\varphi (nm)=\varphi(n)\varphi(m)$。

当 n 为奇数时

当 n 为奇数时，$\varphi (2 \ast n)=\varphi (n)$。

证明：很显然，$\varphi(2\ast n)=\varphi(2) \ast \varphi(n)=\varphi(n)$。

p 整除 n/p 时

\varphi(n)=\varphi(n/p)\ast p \text{，当 }p|(n/p) 。

证明：因为 $p|(n/p)$ ，所以 n 和 n/p 有相同的质因子，即 $r_1=r_2$ 并且 $\forall p_i=p_j$ 。于是：

\displaystyle
\varphi (n/p)=n/p \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i}) \\
\varphi (n)=n \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i})= p \ast n/p \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i}) = p\ast \varphi(n/p)

φ(n)=φ(n/p)*(p-1)

当 $(p,n/p)=1$，并且 $p$ 是质数时。

\varphi(n)=\varphi(n/p)\ast(p-1)

证明：因为 p 是质数，所以 $\varphi(p)=p-1$ 。则：

\varphi(n/p)\ast(p-1) = \varphi(n/p)\ast \varphi(p) =\varphi(n)

n 的所有因子欧拉函数之和为 n

\displaystyle \sum_{d|n} \varphi(d)=n

证明：设 $\displaystyle f(n) = \sum_{d|n} \varphi(d)$，并且 $(n,m)=1$，则有：

\displaystyle f(nm)=\sum_{d|nm} \varphi(d)=(\sum_{d|n}\varphi(d))\ast(\sum_{d|m}\varphi(d)) = f(n)\ast f(m)

所以 $f(n)$ 是积性函数。

\displaystyle f(p^m)=\sum_{d|p^m} \varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+\dots+\varphi(p^m)=1+(p-1)+(p^2-p)+\dots+(p^m-p^{m-1})=p^m

因此我们可以将 n 进行标准分解，可以得到：

\displaystyle f(n)=\prod_{i=1}^{m} f(p_i^{c_i})=\prod_{i=1}^{m} p_i^{c_i}=n \text{，即 } \displaystyle \sum_{d|n} \varphi(d)=n

参考

欧拉函数公式及其证明_百度文库
欧拉函数 | GoAway's Blog