欧拉函数的一个性质及其证明

2024-11-08 来源：个人技术集锦

性质

欧拉函数φ(n)指小于或等于n的正整数中与n互质的数的数目，假设

n = p e 1 1 * p e 2 2 * \cdot \cdot \cdot * p e k k （ p i 是 质 数 (1 < = i < = k) ）

$n=p_{1}^{e_{1}}*p_{2}^{e_{2}}*···*p_{k}^{e_{k}}（p_{i}是质数(1<=i<=k)）$ 那么

φ (n) = (p 1 - 1) p e 1 - 1 1 * (p 2 - 1) p e 2 - 1 2 * \cdot \cdot * (p k - 1) p e k - 1 k \cdot

$φ(n)=(p_{1}-1)p_{1}^{e_{1}-1}*(p_{2}-1)p_{2}^{e_{2}-1}*··*(p_{k}-1)p_{k}^{e_{k}-1}·$ 其中

\sum d | n φ (d) = n

$\sum_{d|n}φ(d)=n$

证明

令函数

f (n) = \sum d | n φ (d)

$f(n)=\sum_{d|n}φ(d)$ 因此

f (p e i i) = φ (1) + φ (p i) + φ (p 2 i) + \cdot \cdot \cdot + φ (p e i i) = 1 + p i - 1 + p 2 i - p i + \cdot \cdot \cdot + p e i i - p e i - 1 i = p e i i （ p i 是 质 数 (1 < = i < = k) ）

$f(p_{i}^{e_{i}})=φ(1)+φ(p_{i})+φ(p_{i}^{2})+···+φ(p_{i}^{e_{i}})=1+p_{i}-1+p_{i}^{2}-p_{i}+···+p_{i}^{e_{i}}-p_{i}^{e_{i}-1}=p_{i}^{e_{i}}（p_{i}是质数(1<=i<=k)）$ 因为φ(n)是积性函数，所以f(n)也是积性函数（这里没证明）。
假设

n = p e 1 1 * p e 2 2 * \cdot \cdot \cdot * p e k k

$n=p_{1}^{e_{1}}*p_{2}^{e_{2}}*···*p_{k}^{e_{k}}$ 所以

\sum d | n φ (d) = f (n) = f (p e 1 1 * p e 2 2 * \cdot \cdot \cdot * p e k k) = f (p e 1 1) * f (p e 2 2) * \cdot \cdot \cdot * f (p e k k) = p e 1 1 * p e 2 2 * \cdot \cdot \cdot * p e k k = n

$\sum_{d|n}φ(d)=f(n)=f(p_{1}^{e_{1}}*p_{2}^{e_{2}}*···*p_{k}^{e_{k}})=f(p_{1}^{e_{1}})*f(p_{2}^{e_{2}})*···*f(p_{k}^{e_{k}})=p_{1}^{e_{1}}*p_{2}^{e_{2}}*···*p_{k}^{e_{k}}=n$

显示全文

全部栏目

欧拉函数的一个性质及其证明

性质

证明