8

试证：当 $ω(n)>1$ 时，$\sum_{d \mid n} μ(d) \log d=0$；一般若 $m \geqslant 1$ 且 $ω(n)>m$，则 $\sum_{d \mid n} μ(d) \log ^m d=0$。

证明： 由于若 $d$ 存在平方因子，则 $μ(d)=0$，不妨设

$$n=p_1p_2\cdots p_k$$

其中 $p_i,p_j(i\neq j)$ 为互异素因子。

1. 当 $ω(n)>1$ 时，$\sum\limits_{d|n}μ(d)\log d=0$。

   $k=ω(n)>1\implies k>1$

   $$\begin{align} \sum\limits_{d|n}μ(d)\log d&=\sum\limits_{S\subseteq\{p_1,p_2,\cdots,p_k\}}μ(\prod\limits_{p\in S}p)\log(\prod\limits_{p\in S}p)\\ &=\sum\limits_{S\subseteq\{p_1,p_2,\cdots,p_k\}}(-1)^{|S|}\sum\limits_{p\in S}\log p \end{align}$$

   交换求和次序，有：

   $$\sum\limits_{d|n}μ(d)\log d=\sum\limits_{p|n}\log p\sum\limits_{\substack{d \mid n \\ p|d}}μ(d)$$

   固定 $p$，则

   $$\begin{align} \sum\limits_{\substack{d \mid n\\ p \mid d}}μ(d)&=(-1)\left[(-1)^0\binom{k-1}{0}+(-1)^1\binom{k-1}{1}+\cdots+(-1)^{k-1}\binom{k-1}{k-1}\right]\\ &=(-1)(-1+1)^{k-1}\\ &=0 \end{align}$$

   因此，

   $$\sum\limits_{d|n}μ(d)\log d=0$$

2. 若 $m \geq 1$，且 $ω(n)>m$，则 $\sum\limits_{d|n}μ(d)\log^m d=0$。

   $k=ω(n)>m\geq 1\implies k>1$

   $$\sum\limits_{d|n}μ(d)\log^m d=\sum\limits_{d|n}μ(d)\sum\limits_{\substack{p_1|d,\cdots,p_m|d \\ p_{i} \mid n}}\log p_1\cdots\log p_m$$

   交换求和次序，有：

   $$\sum\limits_{d|n}μ(d)\log^m d=\sum\limits_{p_1|n}\cdots\sum\limits_{p_m|n}\log p_1\cdots\log p_m\sum\limits_{\substack{d \mid n\\ p_1|d,\cdots,p_m|d} }μ(d)$$

   固定 $p_1,p_2,\cdots,p_m$，令 $S=\{s:s=p_i,i=1,2,\cdots,m\}$ 为其中不同素因子的集合；设 $r=|S|$，则 $r\leq m<k$。

   则：

   $$\begin{align} &\sum\limits_{\substack{d \mid n \\p_1|d,\cdots,p_m|d}}μ(d)\\ &=(-1)^r\left[(-1)^0\binom{k-r}{0}+(-1)^1\binom{k-r}{1}+\cdots+(-1)^{k-r}\binom{k-r}{k-r}\right]\\ &=(-1)^r(-1+1)^{k-r}\\ &=0 \end{align}$$

   因此，

   $$\sum\limits_{d|n}μ(d)\log^m d=0$$

10

求 $\sum_{n=1}^{\infty} μ(n!)$ 之值。

解： 对于 $n\geq 4$，有 $2^2=4|n$，故 $μ(n)=0$。

则：

$$\sum\limits_{n=1}^\infty μ(n!)=μ(1)+μ(2)+μ(6)=1+(-1)+(-1)^2=1$$

11

证明：$\sum_{d \mid n} μ^2(d)=2^{ω(n)}$ 及 $\sum_{t \mid n} μ(t) d(t)=(-1)^{ω(n)}$。

证明：

1. 设 $f=μ^2 * u$，则 $f$ 为积性函数，且 $f(n)=\sum\limits_{d|n}μ^2(d)$。

   设 $n=p^α$，则有：

   $$f(p^α)=\begin{cases} 1, & α=0\\ 2, & α\geq 1 \end{cases}$$

   若 $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$，则

   $$f(m)=f(p_1^{α_1})f(p_2^{α_2})\cdots f(p_s^{α_s})=2^{ω(m)}$$

   即

   $$\sum\limits_{d|n}μ^2(d)=2^{ω(n)}$$

2. 设 $g=μ d * u$，则 $g$ 为积性函数，且 $g(n)=\sum\limits_{t|n}μ(t)d(t)$。

   设 $n=p^α$，则有：

   $$g(p^α)=\begin{cases} 1, & α=0\\ -1, & α\geq 1 \end{cases}$$

   若 $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$，则

   $$g(m)=g(p_1^{α_1})g(p_2^{α_2})\cdots g(p_s^{α_s})=(-1)^{ω(m)}$$

   即

   $$\sum\limits_{t|n}μ(t)d(t)=(-1)^{ω(n)}$$

12

试证：$\sum_{d \mid n} μ(d) σ(d)=(-1)^{ω(n)} \prod_{p \mid n} p$ 及 $\sum_{d \mid n} μ(d) φ(d)=(-1)^{ω(n)} \prod_{p \mid n}(p-2)$。

证明：

1. $\sum\limits_{d|n}μ(d)σ(d)=(-1)^{ω(n)}\prod\limits_{p|n}p$。

   设 $f=μ*σ$，则 $f$ 为积性函数，且 $f(n)=\sum\limits_{d|n}μ(d)σ(d)$。

   设 $n=p^α$，则有：

   $$f(p^α)=\begin{cases} 1, & α=0\\ -p, & α\geq 1 \end{cases}$$

   若 $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$，则

   $$f(m)=f(p_1^{α_1})f(p_2^{α_2})\cdots f(p_s^{α_s})=(-1)^{ω(m)}\prod\limits_{p|m}p$$

   即

   $$\sum\limits_{d|n}μ(d)σ(d)=(-1)^{ω(n)}\prod\limits_{p|n}p$$

2. $\sum\limits_{d|n}μ(d)φ(d)=(-1)^{ω(n)}\prod\limits_{p|n}(p-2)$。

   设 $g=μ*φ$，则 $g$ 为积性函数，且 $g(n)=\sum\limits_{d|n}μ(d)φ(d)$。

   设 $n=p^α$，则有：

   $$g(p^α)=\begin{cases} 1, & α=0\\ 2-p, & α\geq 1 \end{cases}$$

   若 $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$，则

   $$g(m)=g(p_1^{α_1})g(p_2^{α_2})\cdots g(p_s^{α_s})=(-1)^{ω(m)}\prod\limits_{p|m}(p-2)$$

   即

   $$\sum\limits_{d|n}μ(d)φ(d)=(-1)^{ω(n)}\prod\limits_{p|n}(p-2)$$

14

（1）设 $n>1$，证明：$\sum_{\substack{1 \leqslant d \leqslant n \\(n, d)=1}} d=\frac{1}{2} n φ(n)$；

（2）设 $n$ 为奇数，证明：$\sum_{\substack{1 \leqslant d \leqslant \frac{n}{2} \\(d, n)=1}} d=\frac{1}{8} n φ(n)-\frac{1}{8} \prod_{p \mid n}(1-p)$。

证明：

1. 若 $n>1$，则

   $$\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}d=\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}d+\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}(n-d)$$

   $$=\frac{1}{2}\sum\limits_{\substack{1\leq d\leq n\\(n,d)=1}}n$$

   $$=\frac{1}{2}nφ(n)$$

2. 设 $S=\sum\limits_{\substack{1\leq d\leq \frac{n}{2}\\(d,n)=1}}d$，则有

   $$S=\sum\limits_{d=1}^{\lfloor \frac{n}{2} \rfloor}d\cdot I((d,n))$$

   其中 $I=μ*u$，故

   $$I((d,n))=\sum\limits_{k|(d,n)}μ(k)$$

   于是，

   $$S=\sum\limits_{d=1}^{\lfloor \frac{n}{2} \rfloor}d\sum\limits_{k|(d,n)}μ(k)$$

   交换求和次序，有

   $$S=\sum\limits_{k|n}μ(k)\sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d$$

   固定 $k$，设 $d=km$，则

   $$\sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d=k\sum\limits_{m=1}^{\lfloor\frac{n}{2k}\rfloor}m=k\cdot\frac{M(M+1)}{2}$$

   其中，$M=\lfloor\frac{n}{2k}\rfloor$。

   而

   $$\lfloor\frac{n}{2k}\rfloor=\lfloor\frac{\frac{n}{k}}{2}\rfloor=\frac{\frac{n}{k}-1}{2}$$

   因此，

   $$\sum\limits_{\substack{1\leq d\leq \lfloor \frac{n}{2} \rfloor\\k|d}}d=k\cdot\frac{\frac{\frac{n}{k}-1}{2}(\frac{\frac{n}{k}-1}{2}+1)}{2}$$

   $$=\frac{n^2-k^2}{8k}$$

   则

   $$S=\sum\limits_{k|n}μ(k)\cdot\frac{n^2-k^2}{8k}$$

   $$=\frac{1}{8}\left(n^2\sum\limits_{k|n}\frac{μ(k)}{k}-\sum\limits_{k|n}μ(k)k\right)$$

   其中，

   $$\sum\limits_{k|n}\frac{μ(k)}{k}=\frac{φ(n)}{n}$$

   $$\sum\limits_{k|n}μ(k)k=\prod\limits_{p|n}(1-p)$$

   于是，

   $$S=\frac{1}{8}\left(n^2\cdot\frac{φ(n)}{n}-\prod\limits_{p|n}(1-p)\right)$$

   $$=\frac{1}{8}nφ(n)-\frac{1}{8}\prod\limits_{p|n}(1-p)$$

16

求出所有使 $φ(n)=24$ 的自然数。

解： 对于 $n\in\mathbb{N}^+$，作如下素因数分解

$$n=p_1^{α_1}p_2^{α_2}\cdots p_k^{α_k}$$

则

$$φ(n)=n\prod\limits_{p|n}(1-\frac{1}{p})$$

$$=p_1^{α_1-1}(p_1-1)p_2^{α_2-1}(p_2-1)\cdots p_k^{α_k-1}(p_k-1)$$

注意到：$24=2^3\times 3$

1. $n=p^k$

   即

   $$p^{k-1}(p-1)=2^3\times 3$$

   无解。

2. $n=p^aq^b$

   即

   $$p^{a-1}(p-1)q^{b-1}(q-1)=2^3\times 3$$

   • $a=1$，$b=1$，则 $(p-1)(q-1)=24$ 而 $24=1\times 24=2\times 12=3\times 8=4\times 6$ 又 $p,q$ 均为素数，故 $(p,q)=(3,13),(5,7)$ 于是 $n=pq=39,35$

   • $a=2$，$b=1$，则 $p(p-1)(q-1)=24$ 故 $(p,q)=(2,13),(3,5)$ 于是 $n=p^2q=52,45$

   • $a=3$，$b=1$，则 $p^2(p-1)(q-1)=24$ 故 $(p,q)=(2,7)$ 于是 $n=p^3q=56$

   • $a=3$，$b=2$，则 $p^2(p-1)q(q-1)=24$ 故 $(p,q)=(2,3)$ 于是 $n=p^3q^2=72$

   • 其他情况，均无解。

3. $n=p^aq^br^c$

   即

   $$p^{a-1}(p-1)q^{b-1}(q-1)r^{c-1}(r-1)=24$$

   • $a=b=c=1$，则 $(p-1)(q-1)(r-1)=24$ 而 $24=1\times 2\times 12=1\times 3\times 8=1\times 4\times 6=2\times 3\times 4$ 故 $(p,q,r)=(2,3,13),(2,5,7)$ 于是 $n=pqr=78,70$

   • $a=2$，$b=c=1$，则 $p(p-1)(q-1)(r-1)=24$ 故 $(p,q,r)=(2,3,7),(3,2,5)$ 于是 $n=p^2qr=84,90$

   • $a=b=2$，$c=1$ 或其它情况，均无解。

4. $n=p^aq^br^cs^t$

   因为若 $n=2\times 3\times 5\times 7=210$，则 $φ(n)=48>24$，故无解。

综上所述，$n$ 所有可能的取值为

$$39,35,52,45,56,72,78,70,84,90$$

共 10 种。

19

求出所有 $4 \nmid φ(n)$ 的自然数 $n$。

解： 对于 $n\in\mathbb{N}^+$，作如下素因数分解

$$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$$

则

$$φ(n)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_m^{k_m-1}(p_m-1)$$

设 $n=2^a\cdot m$，其中 $2^a \mid n$ 而 $2^{a+1} \nmid m$。

由于 $φ(n)$ 为积性函数，于是

$$φ(n)=φ(2^a)\cdot φ(m)$$

1. $a=0$，则 $n$ 为奇数。

   对于 $m$ 作素因数分解 $m=p_1^{b_1}p_2^{b_2}\cdots p_t^{b_t}$，其中 $p_i$ 为奇质数。

   • 若 $p_i\equiv 1\pmod{4}$，则 $p_i-1\equiv 0\pmod{4}$，则 $4|φ(m)$
   • 若 $p_i\equiv 3\pmod{4}$，则 $φ(p_i^{b_i})=p_i^{b_i-1}(p_i-1)\equiv 2\pmod{4}$

   若 $t \leq 2$，则存在 $i,j$ 使得 $4|(p_i-1)(p_j-1)$，故 $4|φ(n)$。 若 $t=0$，则 $n=1$，$φ(1)=1$，有 $4\nmid φ(1)$。 若 $t=1$，则 $n=p^b$，其中 $p\equiv 3\pmod{4}$，故 $φ(p^b)\equiv 2\pmod{4}$。

2. $a=1$，则 $φ(n)=φ(2\cdot m)=φ(2)φ(m)=φ(m)$

   与上一种情况类似，故 $4\nmid φ(n)\Longleftrightarrow n=2$ 或 $n=2\cdot p^k$，其中 $p\equiv 3\pmod{4}$，$k\geq 1$。

3. $a=2$，则 $φ(n)=φ(4\cdot m)=φ(4)φ(m)=2φ(m)$

   比较可知，$4\nmid φ(m)\Longleftrightarrow m=1\Longleftrightarrow n=4$。

4. $a\geq 3$，则 $4|φ(n)$，无解。

综上所述，$n$ 所有可能的取值为

$$1,2,4,p^k,2\cdot p^k$$

其中 $p$ 为素数且 $p\equiv 3\pmod{4}$，$k\geq 1$。

22

设 $Λ(n)$ 为 Mangoldt 函数，且 $ψ(x) = \sum_{n\leq x} Λ(n)$，则

$$\sum_{n\leq x}ψ\left(\frac{x}{n}\right) = \sum_{n\leq x}Λ(n)\left[\frac{x}{n}\right] = \sum_{n\leq x}\log n$$

证明：

1. $$\begin{align} \sum\limits_{n\leq x}ψ\left(\frac{x}{n}\right) &= \sum\limits_{n\leq x}\sum\limits_{m\leq \frac{x}{n}}Λ(m)\\ &= \sum\limits_{m\leq x}Λ(m)\sum\limits_{n\leq \frac{x}{m}}1\\ &= \sum\limits_{m\leq x}Λ(m)\left[\frac{x}{m}\right] \end{align}$$

2. $$\begin{align} \sum\limits_{n\leq x}\log n &= \sum\limits_{n\leq x}\sum\limits_{d|n}Λ(d)\\ &= \sum\limits_{d\leq x}Λ(d)\sum\limits_{k\leq \frac{x}{d}}1\\ &= \sum\limits_{d\leq x}Λ(d)\left[\frac{x}{d}\right] \end{align}$$

24

设 $σ(n)$ 为除数和函数，证明： （1）$σ(n)=n+1$ 的充要条件是 $n$ 为素数； （2）如果 $n$ 为完全数，即 $σ(n)=2n$，则

$$\sum_{d \mid n} \frac{1}{d}=2$$

证明：

1. 必要性显然。

   充分性： 若 $n=1$，则 $σ(1)=1$，而 $1+n=2$，故不满足。 若 $n$ 为合数，则存在 $d$（$d\neq 1$ 且 $d\neq n$）s.t. $d|n$。

   而

   $$σ(n)\geq 1+d+n>1+n$$

   故 $σ(n)\neq 1+n$，矛盾。 因此，$n$ 为素数。

2. $$\sum\limits_{d|n}\frac{1}{d}=\frac{1}{n}\sum\limits_{d|n}\frac{n}{d}=\frac{1}{n}\sum\limits_{d|n}d=\frac{σ(n)}{n}=\frac{2n}{n}=2$$

参考

• https://zhuanlan.zhihu.com/p/543010816

• https://zhuanlan.zhihu.com/p/544792225

• https://zhuanlan.zhihu.com/p/545595129

• https://zhuanlan.zhihu.com/p/546385318

• https://zhuanlan.zhihu.com/p/547333984

• https://zhuanlan.zhihu.com/p/548061254

贡献者: Ming Wei

上一页潘承洞《数论基础》选解：第六章

下一页潘承洞《数论基础》选解：第五章