This blog post is only available in Simplified Chinse.
当 x 为质数 p 的 k 次幂时 欧拉函数是积性函数 当 n 为奇数时 p 整除 n/p 时 φ(n)=φ(n/p)*(p-1) n 的所有因子欧拉函数之和为 n 参考 之前我们已经知道欧拉函数 φ ( n ) \varphi(n) φ ( n ) 的计算公式:
φ ( n ) = n ∗ ∏ i − 1 r ( p i − 1 p i ) \displaystyle \varphi (n)=n \ast \prod_{i-1}^{r} (\frac {p_i-1} {p_i})
φ ( n ) = n ∗ i − 1 ∏ r ( p i p i − 1 )
我们还知道它的两条性质:
如果φ ( x ) \varphi(x) φ ( x ) 中的x是质数 p 的 k 次幂,那么 φ ( x ) = φ ( p k ) = ( p − 1 ) p k − 1 \displaystyle \varphi (x)=\varphi (p^k)=(p-1)p^{k-1} φ ( x ) = φ ( p k ) = ( p − 1 ) p k − 1 ;
欧拉函数是积性函数,如果 x 和 y 互质,则 φ ( x y ) = φ ( x ) φ ( y ) = ( x − 1 ) ( y − 1 ) \varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1) φ ( x y ) = φ ( x ) φ ( y ) = ( x − 1 ) ( y − 1 ) 。
今天我们要证明上述性质,再介绍几条新的性质。
温馨提示:
本文中有大量 KaTeX 公式,请确保浏览器支持,否则卡到超乎你想象。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。
本文隶属⌈ 数论学习系列 ⌋。
本文是 欧拉函数、费马小定理与欧拉定理详解 一文的补充。建议先阅读后者。
当 x 为质数 p 的 k 次幂时
φ ( x ) \varphi(x) φ ( x ) 中的 x 是质数 p 的 k 次幂时:
φ ( x ) = φ ( p k ) = p k − p k − 1 = ( p − 1 ) p k − 1 \displaystyle \varphi (x)=\varphi (p^k)=p^k-p^{k-1}=(p-1)p^{k-1}
φ ( x ) = φ ( p k ) = p k − p k − 1 = ( p − 1 ) p k − 1
**证明:**小于等于 p k p^k p k 的正整数个数为 p k p^k p k 个,
其中和 p p p 不互质的正整数有:1 ∗ p , 2 ∗ p , … , r ∗ p 1 \ast p, 2 \ast p, \dots ,r \ast p 1 ∗ p , 2 ∗ p , … , r ∗ p 。
显然可以得到:r = p k p − 1 = p k − 1 r=\frac {p^k} {p}-1 = p^{k-1} r = p p k − 1 = p k − 1 。剩下的就是与 p p p 互质的。
那么就得到了:φ ( n ) = p k − p k − 1 \varphi (n)=p^k-p^{k-1} φ ( n ) = p k − p k − 1 。
欧拉函数是积性函数
φ ( n m ) = φ ( n ) ∗ φ ( m ) , ( n , m ) = 1 \displaystyle \varphi(nm)=\varphi (n) \ast \varphi (m),(n,m)=1
φ ( nm ) = φ ( n ) ∗ φ ( m ) , ( n , m ) = 1
**证明:**要证明这个公式,我们可以画张表:
1 2 ⋯ r ⋯ m m + 1 m + 2 ⋯ m + r ⋯ 2 m ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ( n − t ) m + 1 ( n − t ) m + 2 ⋯ ( n − t ) m + r ⋯ ( n − t + 1 ) m ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ( n − 1 ) m + 1 ( n − 1 ) m + 2 ⋯ ( n − 1 ) m + r ⋯ n m \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}
1 m + 1 ⋯ ( n − t ) m + 1 ⋯ ( n − 1 ) m + 1 2 m + 2 ⋯ ( n − t ) m + 2 ⋯ ( n − 1 ) m + 2 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ r m + r ⋯ ( n − t ) m + r ⋯ ( n − 1 ) m + r ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ m 2 m ⋯ ( n − t + 1 ) m ⋯ nm
在这张表里,每行都是一个模 n 的完全剩余系 ,其中有 φ ( n ) \varphi(n) φ ( n ) 个与 n 互质的数字;每列都是一个模 m 的完全剩余系,其中有 φ ( m ) \varphi (m) φ ( m ) 个与 m 互质的数字。一个数字要和 nm 互质,那么它就要和 n 互质又和 m 互质。那么一共就有 φ ( n ) φ ( m ) \varphi(n)\varphi(m) φ ( n ) φ ( m ) 个与 nm 互质的数字,也就是说 φ ( n m ) = φ ( n ) φ ( m ) \varphi (nm)=\varphi(n)\varphi(m) φ ( nm ) = φ ( n ) φ ( m ) 。
当 n 为奇数时
当 n 为奇数时,φ ( 2 ∗ n ) = φ ( n ) \varphi (2 \ast n)=\varphi (n) φ ( 2 ∗ n ) = φ ( n ) 。
**证明:**很显然,φ ( 2 ∗ n ) = φ ( 2 ) ∗ φ ( n ) = φ ( n ) \varphi(2\ast n)=\varphi(2) \ast \varphi(n)=\varphi(n) φ ( 2 ∗ n ) = φ ( 2 ) ∗ φ ( n ) = φ ( n ) 。
p 整除 n/p 时
φ ( n ) = φ ( n / p ) ∗ p ,当 p ∣ ( n / p ) 。 \varphi(n)=\varphi(n/p)\ast p \text{,当 }p|(n/p) 。
φ ( n ) = φ ( n / p ) ∗ p ,当 p ∣ ( n / p ) 。
**证明:**因为 p ∣ ( n / p ) p|(n/p) p ∣ ( n / p ) ,所以 n 和 n/p 有相同的质因子,即 r 1 = r 2 r_1=r_2 r 1 = r 2 并且 ∀ p i = p j \forall p_i=p_j ∀ p i = p j 。于是:
φ ( n / p ) = n / p ∗ ∏ i − 1 r ( p i − 1 p i ) φ ( n ) = n ∗ ∏ i − 1 r ( p i − 1 p i ) = p ∗ n / p ∗ ∏ i − 1 r ( p i − 1 p i ) = p ∗ φ ( n / p ) \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 / p ) = n / p ∗ i − 1 ∏ r ( p i p i − 1 ) φ ( n ) = n ∗ i − 1 ∏ r ( p i p i − 1 ) = p ∗ n / p ∗ i − 1 ∏ r ( p i p i − 1 ) = p ∗ φ ( n / p )
φ(n)=φ(n/p)*(p-1)
当 ( p , n / p ) = 1 (p,n/p)=1 ( p , n / p ) = 1 ,并且 p p p 是质数时。
φ ( n ) = φ ( n / p ) ∗ ( p − 1 ) \varphi(n)=\varphi(n/p)\ast(p-1)
φ ( n ) = φ ( n / p ) ∗ ( p − 1 )
**证明:**因为 p 是质数,所以 φ ( p ) = p − 1 \varphi(p)=p-1 φ ( p ) = p − 1 。则:
φ ( n / p ) ∗ ( p − 1 ) = φ ( n / p ) ∗ φ ( p ) = φ ( n ) \varphi(n/p)\ast(p-1) = \varphi(n/p)\ast \varphi(p) =\varphi(n)
φ ( n / p ) ∗ ( p − 1 ) = φ ( n / p ) ∗ φ ( p ) = φ ( n )
n 的所有因子欧拉函数之和为 n
∑ d ∣ n φ ( d ) = n \displaystyle \sum_{d|n} \varphi(d)=n
d ∣ n ∑ φ ( d ) = n
**证明:**设 f ( n ) = ∑ d ∣ n φ ( d ) \displaystyle f(n) = \sum_{d|n} \varphi(d) f ( n ) = d ∣ n ∑ φ ( d ) ,并且 ( n , m ) = 1 (n,m)=1 ( n , m ) = 1 ,则有:
f ( n m ) = ∑ d ∣ n m φ ( d ) = ( ∑ d ∣ n φ ( d ) ) ∗ ( ∑ d ∣ m φ ( d ) ) = f ( n ) ∗ f ( m ) \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 ( nm ) = d ∣ nm ∑ φ ( d ) = ( d ∣ n ∑ φ ( d )) ∗ ( d ∣ m ∑ φ ( d )) = f ( n ) ∗ f ( m )
所以 f ( n ) f(n) f ( n ) 是积性函数。
f ( p m ) = ∑ d ∣ p m φ ( d ) = φ ( 1 ) + φ ( p ) + φ ( p 2 ) + ⋯ + φ ( p m ) = 1 + ( p − 1 ) + ( p 2 − p ) + ⋯ + ( p m − p m − 1 ) = p m \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
f ( p m ) = d ∣ p m ∑ φ ( d ) = φ ( 1 ) + φ ( p ) + φ ( p 2 ) + ⋯ + φ ( p m ) = 1 + ( p − 1 ) + ( p 2 − p ) + ⋯ + ( p m − p m − 1 ) = p m
因此我们可以将 n 进行标准分解,可以得到:
f ( n ) = ∏ i = 1 m f ( p i c i ) = ∏ i = 1 m p i c i = n ,即 ∑ d ∣ n φ ( d ) = 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
f ( n ) = i = 1 ∏ m f ( p i c i ) = i = 1 ∏ m p i c i = n ,即 d ∣ n ∑ φ ( d ) = n
参考
欧拉函数公式及其证明_百度文库
欧拉函数 | GoAway's Blog