This article is translated by AI.

8

Prove: When $ω(n)>1$, $\sum_{d \mid n} μ(d) \log d=0$; generally if $m \geqslant 1$ and $ω(n)>m$, then $\sum_{d \mid n} μ(d) \log ^m d=0$.

Proof: Since if $d$ has a square factor, then $μ(d)=0$, we can assume without loss of generality

$$n=p_1p_2\cdots p_k$$

where $p_i,p_j(i\neq j)$ are distinct prime factors.

1. When $ω(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}$$

   Exchanging the order of summation, we have:

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

   Fix $p$, then

   $$\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}$$

   Therefore,

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

2. If $m \geq 1$, and $ω(n)>m$, then $\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$$

   Exchanging the order of summation, we have:

   $$\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)$$

   Fix $p_1,p_2,\cdots,p_m$, let $S=\{s:s=p_i,i=1,2,\cdots,m\}$ be the set of distinct prime factors among them; let $r=|S|$, then $r\leq m<k$.

   Then:

   $$\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}$$

   Therefore,

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

10

Find the value of $\sum_{n=1}^{\infty} μ(n!)$.

Solution: For $n\geq 4$, we have $2^2=4|n$, so $μ(n)=0$.

Then:

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

11

Prove: $\sum_{d \mid n} μ^2(d)=2^{ω(n)}$ and $\sum_{t \mid n} μ(t) d(t)=(-1)^{ω(n)}$.

Proof:

1. Let $f=μ^2 * u$, then $f$ is a multiplicative function, and $f(n)=\sum\limits_{d|n}μ^2(d)$.

   Let $n=p^α$, then we have:

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

   If $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$, then

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

   That is

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

2. Let $g=μ d * u$, then $g$ is a multiplicative function, and $g(n)=\sum\limits_{t|n}μ(t)d(t)$.

   Let $n=p^α$, then we have:

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

   If $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$, then

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

   That is

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

12

Prove: $\sum_{d \mid n} μ(d) σ(d)=(-1)^{ω(n)} \prod_{p \mid n} p$ and $\sum_{d \mid n} μ(d) φ(d)=(-1)^{ω(n)} \prod_{p \mid n}(p-2)$.

Proof:

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

   Let $f=μ*σ$, then $f$ is a multiplicative function, and $f(n)=\sum\limits_{d|n}μ(d)σ(d)$.

   Let $n=p^α$, then we have:

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

   If $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$, then

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

   That is

   $$\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)$.

   Let $g=μ*φ$, then $g$ is a multiplicative function, and $g(n)=\sum\limits_{d|n}μ(d)φ(d)$.

   Let $n=p^α$, then we have:

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

   If $m=p_1^{α_1}p_2^{α_2}\cdots p_s^{α_s}$, then

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

   That is

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

14

(1) Let $n>1$, prove: $\sum_{\substack{1 \leqslant d \leqslant n \\(n, d)=1}} d=\frac{1}{2} n φ(n)$;

(2) Let $n$ be an odd number, prove: $\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)$.

Proof:

1. If $n>1$, then

   $$\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. Let $S=\sum\limits_{\substack{1\leq d\leq \frac{n}{2}\\(d,n)=1}}d$, then we have

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

   Where $I=μ*u$, so

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

   Thus,

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

   Exchanging the order of summation, we have

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

   Fix $k$, let $d=km$, then

   $$\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}$$

   Where $M=\lfloor\frac{n}{2k}\rfloor$.

   And

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

   Therefore,

   $$\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}$$

   Then

   $$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)$$

   Where,

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

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

   Thus,

   $$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

Find all natural numbers $n$ such that $φ(n)=24$.

Solution: For $n\in\mathbb{N}^+$, make the following prime factorization

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

Then

$$φ(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)$$

Note that: $24=2^3\times 3$

1. $n=p^k$

   That is

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

   No solution.

2. $n=p^aq^b$

   That is

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

   • $a=1$, $b=1$, then $(p-1)(q-1)=24$ And $24=1\times 24=2\times 12=3\times 8=4\times 6$ Also $p,q$ are prime numbers, so $(p,q)=(3,13),(5,7)$ Thus $n=pq=39,35$

   • $a=2$, $b=1$, then $p(p-1)(q-1)=24$ So $(p,q)=(2,13),(3,5)$ Thus $n=p^2q=52,45$

   • $a=3$, $b=1$, then $p^2(p-1)(q-1)=24$ So $(p,q)=(2,7)$ Thus $n=p^3q=56$

   • $a=3$, $b=2$, then $p^2(p-1)q(q-1)=24$ So $(p,q)=(2,3)$ Thus $n=p^3q^2=72$

   • Other cases, no solution.

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

   That is

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

   • $a=b=c=1$, then $(p-1)(q-1)(r-1)=24$ And $24=1\times 2\times 12=1\times 3\times 8=1\times 4\times 6=2\times 3\times 4$ So $(p,q,r)=(2,3,13),(2,5,7)$ Thus $n=pqr=78,70$

   • $a=2$, $b=c=1$, then $p(p-1)(q-1)(r-1)=24$ So $(p,q,r)=(2,3,7),(3,2,5)$ Thus $n=p^2qr=84,90$

   • $a=b=2$, $c=1$ or other cases, no solution.

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

   Because if $n=2\times 3\times 5\times 7=210$, then $φ(n)=48>24$, so no solution.

In summary, all possible values of $n$ are

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

A total of 10 kinds.

19

Find all natural numbers $n$ such that $4 \nmid φ(n)$.

Solution: For $n\in\mathbb{N}^+$, make the following prime factorization

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

Then

$$φ(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)$$

Let $n=2^a\cdot m$, where $2^a \mid n$ and $2^{a+1} \nmid m$.

Since $φ(n)$ is a multiplicative function, then

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

1. $a=0$, then $n$ is an odd number.

   For $m$, make prime factorization $m=p_1^{b_1}p_2^{b_2}\cdots p_t^{b_t}$, where $p_i$ is an odd prime number.

   • If $p_i\equiv 1\pmod{4}$, then $p_i-1\equiv 0\pmod{4}$, then $4|φ(m)$
   • If $p_i\equiv 3\pmod{4}$, then $φ(p_i^{b_i})=p_i^{b_i-1}(p_i-1)\equiv 2\pmod{4}$

   If $t \leq 2$, then there exist $i,j$ such that $4|(p_i-1)(p_j-1)$, so $4|φ(n)$. If $t=0$, then $n=1$, $φ(1)=1$, we have $4\nmid φ(1)$. If $t=1$, then $n=p^b$, where $p\equiv 3\pmod{4}$, so $φ(p^b)\equiv 2\pmod{4}$.

2. $a=1$, then $φ(n)=φ(2\cdot m)=φ(2)φ(m)=φ(m)$

   Similar to the previous case, so $4\nmid φ(n)\Longleftrightarrow n=2$ or $n=2\cdot p^k$, where $p\equiv 3\pmod{4}$, $k\geq 1$.

3. $a=2$, then $φ(n)=φ(4\cdot m)=φ(4)φ(m)=2φ(m)$

   By comparison, $4\nmid φ(m)\Longleftrightarrow m=1\Longleftrightarrow n=4$.

4. $a\geq 3$, then $4|φ(n)$, no solution.

In summary, all possible values of $n$ are

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

Where $p$ is a prime number and $p\equiv 3\pmod{4}$, $k\geq 1$.

22

Let $Λ(n)$ be the Mangoldt function, and $ψ(x) = \sum_{n\leq x} Λ(n)$, then

$$\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$$

Proof:

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

Let $σ(n)$ be the divisor sum function, prove: (1) The necessary and sufficient condition for $σ(n)=n+1$ is that $n$ is a prime number; (2) If $n$ is a perfect number, i.e., $σ(n)=2n$, then

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

Proof:

1. Necessity is obvious.

   Sufficiency: If $n=1$, then $σ(1)=1$, and $1+n=2$, so it is not satisfied. If $n$ is a composite number, then there exists $d$ ($d\neq 1$ and $d\neq n$) s.t. $d|n$.

   And

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

   So $σ(n)\neq 1+n$, contradiction. Therefore, $n$ is a prime number.

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$$

References

• 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

Contributors: Ming Wei

Previous pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 6

Next pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 5