之前我们已经知道欧拉函数 \varphi(n) 的计算公式:
我们还知道它的两条性质:
如果\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 次幂时:
证明:小于等于 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}。
欧拉函数是积性函数
证明:要证明这个公式,我们可以画张表:
\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 时
证明:因为 p|(n/p) ,所以 n 和 n/p 有相同的质因子,即 r_1=r_2 并且 \forall p_i=p_j 。于是:
\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 是质数时。
证明:因为 p 是质数,所以 \varphi(p)=p-1 。则:
n 的所有因子欧拉函数之和为 n
证明:设 \displaystyle f(n) = \sum_{d|n} \varphi(d),并且 (n,m)=1,则有:
所以 f(n) 是积性函数。
因此我们可以将 n 进行标准分解,可以得到:
参考
欧拉函数公式及其证明_百度文库
欧拉函数 | GoAway's Blog
本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://old.skywt.cn/posts/phinplus/