中科大计算机数学作业解答三（参考书：具体数学）

Problem 1.

(a) 给出$\pi (2n)$的下界

( 2 n ) π ( 2 n ) ≥ C 2 n n ≥ 2 2 n 2 n (2n)^{π(2n)}\geq{}C_{2n}^n\geq{}\frac{2^{2n}}{2n} (2n)π(2n)≥C2nn​≥2n22n​

对不等式两端取对数则有
π ( 2 n ) l o g 2 ( 2 n ) ≥ 2 n l o g 2 ( 2 ) − l o g 2 ( 2 n ) π ( 2 n ) ≥ 2 n l o g 2 2 n − 1 π(2n)log_2(2n)\geq{}2nlog_2(2)-log_2(2n)\\ π(2n)\geq{}\frac{2n}{log_22n}-1 π(2n)log2​(2n)≥2nlog2​(2)−log2​(2n)π(2n)≥log2​2n2n​−1

(b) 给出$\pi (2n)$的上界

( n ) π ( 2 n ) − π ( n ) ≤ C 2 n n ≤ 2 2 n (n)^{π(2n)-π(n)}\leq{}C_{2n}^n\leq{}2^{2n} (n)π(2n)−π(n)≤C2nn​≤22n

对不等式两端取对数有
π ( 2 n ) − π ( n ) ≤ 2 n l o g 2 n π(2n)-π(n)\leq\frac{2n}{log_2n} π(2n)−π(n)≤log2​n2n​
假设有 π ( n ) ≤ 4 n l o g 2 n π(n)\leq{}\frac{4n}{log_2n} π(n)≤log2​n4n​,下面使用数学归纳法证明

（1）$n=1,2,3$时，可以验证该假设成立

（2）假设$x<n$时有 π ( x ) ≤ 4 x l o g 2 x π(x)\leq{}\frac{4x}{log_2x} π(x)≤log2​x4x​成立，当$x=n$时有

1.$n=2k$

π ( n ) = π ( 2 k ) ≤ π ( k ) + 2 k l o g 2 k ≤ 4 k l o g 2 k + 2 k l o g 2 k = 6 k l o g 2 k = 3 n l o g 2 n 2 ≤ 4 n l o g 2 n ( 1 ) \begin{aligned} π(n)=π(2k)&\leq{}π(k)+\frac{2k}{log_2k}\\ &\leq{}\frac{4k}{log_2k}+\frac{2k}{log_2k}\\ &=\frac{6k}{log_2k}\\ &=\frac{3n}{log_2\frac{n}{2}}\\ &\leq{}\frac{4n}{log_2n} \quad\quad(1) \end{aligned} π(n)=π(2k)​≤π(k)+log2​k2k​≤log2​k4k​+log2​k2k​=log2​k6k​=log2​2n​3n​≤log2​n4n​(1)​

1.$n=2k+1$

π ( n ) = π ( 2 k + 1 ) ≤ π ( 2 k ) + 1 ≤ 6 k l o g 2 k + 1 = 3 n l o g 2 n 2 + 1 ≤ 4 n l o g 2 n ( 2 ) \begin{aligned} π(n)=π(2k+1)&\leq{}π(2k)+1\\ &\leq{}\frac{6k}{log_2k}+1\\ &=\frac{3n}{log_2\frac{n}{2}}+1\\ &\leq{}\frac{4n}{log_2n} \quad\quad(2) \end{aligned} π(n)=π(2k+1)​≤π(2k)+1≤log2​k6k​+1=log2​2n​3n​+1≤log2​n4n​(2)​

对上面证明的（1），（2）式解释，可以简单验证，在 n ≥ 2 5 n\geq{}2^5 n≥25情况下，对该式左右同时求导，易验证右式导数大于左式，同时 n = 2 5 n=2^5 n=25的情况下，原式成立，因此该推导在 n ≥ 2 5 n\geq{}2^5 n≥25的情况下是成立的，在 n < 2 5 n<2^5 n<25的情况下，也可以手动验证，也是成立的，这里不再一一验证，实际上$\pi (n)$的下界应该近似于 n / l n n n/ln_n n/lnn​

故由数学退归纳法证明 π ( n ) ≤ 4 n l o g 2 n π(n)\leq{}\frac{4n}{log_2n} π(n)≤log2​n4n​,$\pi (2n)$的下界有
π ( 2 n ) ≤ 8 n l o g 2 2 n π(2n)\leq{}\frac{8n}{log_22n} π(2n)≤log2​2n8n​

© 证明任意$[n,6n]$内有一个素数

π ( 6 n ) − π ( n ) ≥ 6 n l o g 2 6 n − 1 − 4 n l o g 2 n ≥ 1 对右边移项也就是 6 n l o g 2 6 n ≥ 4 n l o g 2 n + 2 π(6n)-π(n)\geq{}\frac{6n}{log_26n}-1-\frac{4n}{log_2n}\geq1\\ 对右边移项也就是\\ \frac{6n}{log_26n}\geq\frac{4n}{log_2n}+2 π(6n)−π(n)≥log2​6n6n​−1−log2​n4n​≥1对右边移项也就是log2​6n6n​≥log2​n4n​+2

与问题(b)归纳步骤证明类似，通过求导可以知道，在 n ≥ 2 10 n\geq{}2^{10} n≥210的情况下，该式显然成立，在 n < 2 10 n<2^{10} n<210的情况下，可以通过逐个列出n验证，也是成立的，后续证明有$[n,2n]$范围内必会有一素数，因此这里略过

(d)题目要求证明的三个条件显然不准确，因此依次证明以下三个条件

1) l p = 0 , f o r p ∈ ( 2 n 3 , n ] l_p=0,for \quad p \in (\frac{2n}{3},n] lp​=0,forp∈(32n​,n],题目对p范围划分不对

( 2 n n ) = ( 2 n ) ! ( n ! ) 2 , ∀ p ∈ [ 2 n 3 , n ] , {\displaystyle {\binom {2n}{n}}}=\frac{(2n)!}{(n!)^2},\forall p\in [\frac{2n}{3},n], (n2n​)=(n!)2(2n)!​,∀p∈[32n​,n],必然$p$在分母出现两次，$p$在分子出现一次，$2p$在分子出现一次，$x\ge 3时，xp$不会出现在分子，因此约分后，$p$不会出现在该式中。原命题得证

2) l p ≤ 1 , f o r p ∈ ( 2 n , 2 n 3 ] l_p\leq{1},for \quad p \in (\sqrt{2n},\frac{2n}{3}] lp​≤1,forp∈(2n ​,32n​]，题目中 2 n \sqrt{2n} 2n ​不在这个范围内

根据公式4.25有$p$对$n!$的贡献为 ∑ j ≥ 1 ⌊ n p j ⌋ \displaystyle \sum_{j\geq{1}}\lfloor \frac{n}{p^j}\rfloor j≥1∑​⌊pjn​⌋

所以对于 ( 2 n n ) = ( 2 n ) ! ( n ! ) 2 \displaystyle {\binom {2n}{n}}=\frac{(2n)!}{(n!)^2} (n2n​)=(n!)2(2n)!​有 l p = ∑ j ≥ 1 ⌊ 2 n p j ⌋ − 2 ∑ j ≥ 1 ⌊ n p j ⌋ = ∑ j ≥ 1 ( ⌊ 2 n p j ⌋ − 2 ⌊ n p j ⌋ ) l^p=\displaystyle \sum_{j\geq{1}}\lfloor \frac{2n}{p^j}\rfloor-2\sum_{j\geq{1}}\lfloor \frac{n}{p^j}\rfloor=\sum_{j\geq{1}}(\lfloor \frac{2n}{p^j}\rfloor-2\lfloor \frac{n}{p^j}\rfloor) lp=j≥1∑​⌊pj2n​⌋−2j≥1∑​⌊pjn​⌋=j≥1∑​(⌊pj2n​⌋−2⌊pjn​⌋)

括号内内容只可能为0或1， n p j m o d 1 < 1 2 \frac{n}{p^j}\ mod \ 1<\frac{1}{2} pjn​ mod 1<21​时为0， n p j m o d 1 ≥ 1 2 \frac{n}{p^j}\ mod \ 1\geq\frac{1}{2} pjn​ mod 1≥21​时为1.同时， j > l o g p ( 2 n ) j>log_p(2n) j>logp​(2n)时，括号内也为0，因此有 l p ≤ l o g p 2 n l_p\leq{log_p{2n}} lp​≤logp​2n,以及 p l p ≤ p l o g p 2 n = 2 n p^{l_p}\leq{p^{log_p{2n}}}=2n plp​≤plogp​2n=2n

因此任何素数p对于 ( 2 n n ) {\displaystyle {\binom {2n}{n}}} (n2n​)的贡献小于$2n$

因此 l p ≤ 1 , f o r p ∈ ( 2 n , 2 n 3 ] l_p\leq{1},for \quad p \in (\sqrt{2n},\frac{2n}{3}] lp​≤1,forp∈(2n ​,32n​]

3) ∏ p ≤ n p ≤ 2 2 n \displaystyle \prod_{p\leq{n}}p\leq2^{2n} p≤n∏​p≤22n，题目范围显然不正确，如反例n=11，题目中左式为210，右式约为166

令 f ( x ) = ∏ p ≤ x p ， p f(x)=\prod_{p\leq{x}}p，p f(x)=∏p≤x​p，p为素数

对于 C 2 n n = ∏ p ≤ 2 n p l p \displaystyle C_{2n}^n=\prod_{p\leq{2n}}p^{l_p} C2nn​=p≤2n∏​plp​来说，$\forall p\in (n,2n]$,其 l p l_p lp​显然为1，因为对比式子 ( 2 n ) ! ( n ! ) 2 \frac{(2n)!}{(n!)^2} (n!)2(2n)!​,p出现在分子中，而不会出现在分母中，因此无法将其约分，所以有：
C 2 n − 1 n = ∏ p ≤ 2 n − 1 p l p ≥ ∏ n < p ≤ 2 n − 1 p l p = ∏ n < p ≤ 2 n − 1 p = f ( 2 n − 1 ) f ( n ) \displaystyle C_{2n-1}^{n}=\prod_{p\leq{2n-1}}p^{l_p}\geq{}\prod_{nC2n−1n​=p≤2n−1∏​plp​≥n<p≤2n−1∏​plp​=n<p≤2n−1∏​p=f(n)f(2n−1)​

又有：
C 2 n − 1 n = 1 2 ( C 2 n − 1 n + C 2 n − 1 n − 1 ) < 1 2 ( 1 + 1 ) 2 n − 1 = 2 2 n − 2 C^n_{2n-1}=\frac{1}{2}(C_{2n-1}^n+C_{2n-1}^{n-1})<\frac{1}{2}(1+1)^{2n-1}=2^{2n-2} C2n−1n​=21​(C2n−1n​+C2n−1n−1​)<21​(1+1)2n−1=22n−2
因此有
f ( 2 n − 1 ) f ( n ) < 2 2 n − 2 \frac{f(2n-1)}{f(n)}<2^{2n-2} f(n)f(2n−1)​<22n−2
现在用数学归纳法证明，

（1)$n=1,2,3$时， f ( n ) < 2 2 n f(n)<2^{2n} f(n)<22n显然成立

（2)假设 x < n 时，有 f ( x ) ≤ 2 2 x xx<n时，有f(x)≤22x成立，则$x=n$时有

1）$n=2m-1$时，

f ( n ) = f ( 2 m − 1 ) < 2 2 m − 2 f ( m ) ≤ 2 2 m − 2 2 2 m = 2 4 m − 2 = 2 2 n f(n)=f(2m-1){}<2^{2m-2}f(m)\leq{}2^{2m-2}2^{2m}=2^{4m-2}=2^{2n} f(n)=f(2m−1)<22m−2f(m)≤22m−222m=24m−2=22n

1）$n=2m$时，

f ( n ) = f ( 2 m ) = f ( 2 m − 1 ) < 2 4 m − 2 = 2 2 n − 2 < 2 2 n f(n)=f(2m)=f(2m-1)<2^{4m-2}=2^{2n-2}<2^{2n} f(n)=f(2m)=f(2m−1)<24m−2=22n−2<22n

故根据数学归纳法，原命题成立。

4）现在开始证明对于任意n有一个素数在[n,2n]

假设在这个范围内并不存在素数，那么有

1.$[n,2n]$不存在素数

2. ( 2 n 3 , n ] (\frac{2n}{3},n] (32n​,n]不存在素数，根据证明1）

3. ( 2 n , 2 n 3 ] (\sqrt{2n},\frac{2n}{3}] (2n ​,32n​]范围内的素数指数最大为1，根据证明2
4 n 2 n ≤ ( 2 n n ) = ( ∏ p ≤ 2 n p l p ) = ( ∏ p ≤ 2 n p l p ) ( ∏ 2 n < p ≤ 2 n 3 p ) ≤ ( 2 n ) 2 n ( ∏ 2 n < p ≤ 2 n 3 p ) ( 1 ) ≤ ( 2 n ) 2 n ( ∏ 1 < p ≤ 2 n 3 p ) = ( 2 n ) 2 n ( 2 ) 4 n 3 \begin{aligned} \displaystyle \frac{4^n}{2n}&\leq{\binom {2n}{n}}\\ &=(\prod_{p\leq{2n}}p^{l_p})\\ &=(\prod_{p\leq{\sqrt{2n}}}p^{l_p})(\prod_{\sqrt{2n}2n4n​​≤(n2n​)=(p≤2n∏​plp​)=(p≤2n ​∏​plp​)(2n ​<p≤32n​∏​p)≤(2n)2n ​(2n ​<p≤32n​∏​p)(1)≤(2n)2n ​(1<p≤32n​∏​p)=(2n)2n ​(2)34n​​
对（1）的说明，在这个连乘范围内有不超过 2 n \sqrt{2n} 2n ​个素数，每个素数最多贡献2n，因此连乘小于等于 ( 2 n ) 2 n (2n)^{\sqrt{2n}} (2n)2n ​，对等式两边取对数有

l o g 4 3 n ≤ ( 2 n + 1 ) l o g 2 n \frac{log4}{3}n\leq(\sqrt{2n}+1)log2n 3log4​n≤(2n ​+1)log2n
解得$n<468$,也就是对于$n\ge 468$的情况，上式不成立，即假设$[n,2n]$无素数不成立，下面列出$n<468$范围内，满足$p\in [n,2n]$内间距最大的素数序列

2	3	5	7	13	23	43	83	163	317	631

可以见到也满足任意$p\in [n,2n]$必然存在1素数，因此对于任意n，有一个素数p属于$[n,2n]$

Problem 2 (10 points). Exercise 57 in Chapter 4

按照提示，首先证明 ∑ 1 ≤ m ≤ n ∑ d ∖ m ϕ ( d ) = ∑ d ≥ 1 ϕ ( d ) ⌊ n d ⌋ \displaystyle \sum_{1\leq{m}\leq{n}}\sum_{d\setminus m} \phi(d) = \sum_{d\geq{1}}\phi(d)\lfloor \frac{n}{d}\rfloor 1≤m≤n∑​d∖m∑​ϕ(d)=d≥1∑​ϕ(d)⌊dn​⌋.

∑ 1 ≤ m ≤ n ∑ d ∖ m ϕ ( d ) = ∑ 1 ≤ m ≤ n ∑ 1 ≤ d ≤ m [ d ∖ m ] ϕ ( d ) = ∑ 1 ≤ m ≤ n ∑ 1 ≤ d [ d ∖ m ] ϕ ( d ) d > m 使 [ d ∖ m ] = 0 ，因此可以去掉上界 = ∑ 1 ≤ d ∑ 1 ≤ m ≤ n [ d ∖ m ] ϕ ( d ) d 与 m 无关，交换次序 = ∑ 1 ≤ d ∑ 1 ≤ k ≤ n d [ m = d k ] ϕ ( d ) m 换成 d k = ∑ 1 ≤ d ⌊ n d ⌋ ϕ ( d ) [ m = d k ] 必然满足，因此叠加为 n d \begin{aligned} \displaystyle \sum_{1\leq{m}\leq{n}}\sum_{d\setminus m} \phi(d) &= \sum_{1\leq{m}\leq{n}}\sum_{1\leq{d}\leq{m}}[d\setminus m]\phi(d) \\ &=\sum_{1\leq{m}\leq{n}}\sum_{1\leq{d}}[d\setminus m]\phi(d) \quad d>m使[d\setminus m]=0，因此可以去掉上界\\ &=\sum_{1\leq{d}}\sum_{1\leq{m}\leq{n}}[d\setminus m]\phi(d) \quad d与m无关，交换次序\\ &=\sum_{1\leq{d}}\sum_{1\leq{k}\leq{\frac{n}{d}}}[m=dk]\phi(d) \quad m换成dk\\ &=\sum_{1\leq{d}}\lfloor \frac{n}{d} \rfloor \phi(d) \quad [m=dk]必然满足，因此叠加为\frac{n}{d} \\ \end{aligned} 1≤m≤n∑​d∖m∑​ϕ(d)​=1≤m≤n∑​1≤d≤m∑​[d∖m]ϕ(d)=1≤m≤n∑​1≤d∑​[d∖m]ϕ(d)d>m使[d∖m]=0，因此可以去掉上界=1≤d∑​1≤m≤n∑​[d∖m]ϕ(d)d与m无关，交换次序=1≤d∑​1≤k≤dn​∑​[m=dk]ϕ(d)m换成dk=1≤d∑​⌊dn​⌋ϕ(d)[m=dk]必然满足，因此叠加为dn​​

原式得证，令 g ( n ) = ∑ 1 ≤ m ≤ n ∑ d ∖ m ϕ ( d ) = ∑ d ≥ 1 ϕ ( d ) ⌊ n d ⌋ \displaystyle g(n)= \sum_{1\leq{m}\leq{n}}\sum_{d\setminus m} \phi(d)=\sum_{d\geq{1}}\phi(d)\lfloor \frac{n}{d}\rfloor g(n)=1≤m≤n∑​d∖m∑​ϕ(d)=d≥1∑​ϕ(d)⌊dn​⌋ ，

根据公式4.54有 g ( n ) = ∑ 1 ≤ m ≤ n ∑ d ∖ m ϕ ( d ) = ∑ 1 ≤ m ≤ n m = n ( n + 1 ) 2 \displaystyle g(n) = \sum_{1\leq{m}\leq{n}}\sum_{d\setminus m} \phi(d) = \sum_{1\leq{m}\leq{n}} m = \frac{n(n+1)}{2} g(n)=1≤m≤n∑​d∖m∑​ϕ(d)=1≤m≤n∑​m=2n(n+1)​

因为 r 1 = m m o d d , r 2 = n m o d d r_1=m\ mod\ d,r_2=n\ mod\ d r1​=m mod d,r2​=n mod d，所以有
⌊ m + n d ⌋ − ⌊ m d ⌋ − ⌊ n d ⌋ = ⌊ r 1 + r 2 d ⌋ = { 0 ， r 1 + r 2 < d 1 ， r 1 + r 2 ≥ d \lfloor \frac{m+n}{d}\rfloor-\lfloor \frac{m}{d}\rfloor-\lfloor \frac{n}{d}\rfloor=\lfloor \frac{r_1+r_2}{d}\rfloor=\left\{\begin{matrix}0，r_1+r_2< d\\1，r_1+r_2\geq d \end{matrix}\right. ⌊dm+n​⌋−⌊dm​⌋−⌊dn​⌋=⌊dr1​+r2​​⌋={0，r1​+r2​<d1，r1​+r2​≥d​

∑ k ∈ S ( m , n ) ϕ ( k ) = g ( m + n ) − g ( m ) − g ( n ) = ∑ d ≥ 1 ϕ ( d ) ( ⌊ m + n d ⌋ − ⌊ m d ⌋ − ⌊ n d ⌋ ) = ( m + n + 1 ) ( m + n ) 2 − ( m + 1 ) m 2 − ( n + 1 ) n 2 = m n \begin{aligned} \displaystyle \sum_{k\in S(m,n)} \phi(k)&=g(m+n)-g(m)-g(n)\\ &=\sum_{d\geq{1}}\phi(d)(\lfloor \frac{m+n}{d}\rfloor-\lfloor \frac{m}{d}\rfloor-\lfloor \frac{n}{d}\rfloor)\\ &=\frac{(m+n+1){(m+n)}}{2} -\frac{(m+1){m}}{2} -\frac{(n+1){n}}{2}\\ &=mn \end{aligned} k∈S(m,n)∑​ϕ(k)​=g(m+n)−g(m)−g(n)=d≥1∑​ϕ(d)(⌊dm+n​⌋−⌊dm​⌋−⌊dn​⌋)=2(m+n+1)(m+n)​−2(m+1)m​−2(n+1)n​=mn​

所以原式得证。

Problem 3 (20 points). Exercise 50 in Chapter 4.

a）设 Ψ m ( z ) = ∏ 0 ≤ k < m , k ⊥ m ( z − w k ) ，证明 z m − 1 = ∏ d ∖ m Ψ d ( z ) \displaystyle \Psi_{m}(z) = \prod_{0\leq{k}Ψm​(z)=0≤k<m,k⊥m∏​(z−wk)，证明zm−1=d∖m∏​Ψd​(z)

1)对于任意$f(x)$有

∏ 0 ≤ k < m f ( k ) = ∏ d ∖ m ∏ 0 ≤ k < m f ( k ) [ d = g c d ( k , m ) ] = ∏ d ∖ m ∏ 0 ≤ k < m f ( k ) [ k d ⊥ m d ] = ∏ d ∖ m ∏ 0 ≤ k < m d f ( k d ) [ k ⊥ m d ] 用 k d 替换 k = ∏ d ∖ m ∏ 0 ≤ k < d f ( k m d ) [ k ⊥ d ] 公式 4.7 \begin{aligned} \displaystyle \prod_{0\leq{k}0≤k<m∏​f(k)​=d∖m∏​0≤k<m∏​f(k)[d=gcd(k,m)]=d∖m∏​0≤k<m∏​f(k)[dk​⊥dm​]=d∖m∏​0≤k<dm​∏​f(kd)[k⊥dm​]用kd替换k=d∖m∏​0≤k<d∏​f(dkm​)[k⊥d]公式4.7​

2）令 f ( x ) = z − w k f(x)=z-w^k f(x)=z−wk,则有

2 m − 1 = ∏ 0 ≤ k < m ( z − w k ) = ∏ d ∖ m ∏ 0 ≤ k < d ( z − w k m d ) [ k ⊥ d ] = ∏ d ∖ m ∏ 0 ≤ k < d , k ⊥ d ( z − w k m d ) = ∏ d ∖ m ∏ 0 ≤ k < m , k ⊥ m ( z − w k ) 用 k 替换 k m d = ∏ d ∖ m Ψ d ( z ) \begin{aligned} \displaystyle 2^m-1&=\prod_{0\leq{k}2m−1​=0≤k<m∏​(z−wk)=d∖m∏​0≤k<d∏​(z−wdkm​)[k⊥d]=d∖m∏​0≤k<d,k⊥d∏​(z−wdkm​)=d∖m∏​0≤k<m,k⊥m∏​(z−wk)用k替换dkm​=d∖m∏​Ψd​(z)​

b）证明 Ψ m ( z ) = ∏ d ∖ m ( z d − 1 ) μ ( m / d ) \displaystyle \Psi_{m}(z) = \prod_{d\setminus m}(z^d-1)^{\mu(m/d)} Ψm​(z)=d∖m∏​(zd−1)μ(m/d)

令 g ( x ) = z x − 1 , f ( x ) = Ψ x ( z ) g(x)=z^x-1,f(x)=\Psi_x(z) g(x)=zx−1,f(x)=Ψx​(z),则a)的结论有原 式有
z m − 1 = ∏ d ∖ m Ψ d ( z ) g ( m ) = ∏ d ∖ m f ( d ) \begin{aligned} \displaystyle z^m-1 &=\prod_{d\setminus m}\Psi_{d}(z)\\ g(m)&=\prod_{d\setminus m}f(d)\\ \end{aligned} zm−1g(m)​=d∖m∏​Ψd​(z)=d∖m∏​f(d)​
那么
∏ d ∖ m ( z d − 1 ) μ ( m d ) = ∏ d ∖ m ( g ( d ) ) μ ( m d ) = ∏ d ∖ m ( ∏ k ∖ d f ( k ) ) μ ( m d ) \begin{aligned} \displaystyle \prod_{d\setminus m}(z^d-1)^{\mu(\frac{m}{d})} &=\prod_{d\setminus m}(g(d))^{\mu(\frac{m}{d})}\\ &=\prod_{d\setminus m}(\prod_{k\setminus d}f(k))^{\mu(\frac{m}{d})}\\ \end{aligned} d∖m∏​(zd−1)μ(dm​)​=d∖m∏​(g(d))μ(dm​)=d∖m∏​(k∖d∏​f(k))μ(dm​)​
现在对这个式子使用lg运算则有
l g ( ∏ d ∖ m ( ∏ k ∖ d f ( k ) ) μ ( m d ) ) = ∑ d ∖ m { l g [ ∏ k ∖ d f ( k ) ] μ ( m d ) } = ∑ d ∖ m μ ( m d ) l g ( ∏ k ∖ d f ( k ) ) = ∑ d ∖ m μ ( m d ) ∑ k ∖ d l g ( f ( k ) ) = l g ( f ( m ) ) 根据公式 4.56 证明过程 \begin{aligned} \displaystyle lg(\prod_{d\setminus m}(\prod_{k\setminus d}f(k))^{\mu(\frac{m}{d})})&=\sum_{d\setminus m}\{lg[\prod_{k\setminus d}f(k)]^{\mu(\frac{m}{d})}\}\\ &=\sum_{d\setminus m}\mu(\frac{m}{d})lg(\prod_{k\setminus d}f(k))\\ &=\sum_{d\setminus m}\mu(\frac{m}{d})\sum_{k\setminus d}lg(f(k))\\ &=lg(f(m)) \quad 根据公式4.56证明过程 \end{aligned} lg(d∖m∏​(k∖d∏​f(k))μ(dm​))​=d∖m∑​{lg[k∖d∏​f(k)]μ(dm​)}=d∖m∑​μ(dm​)lg(k∖d∏​f(k))=d∖m∑​μ(dm​)k∖d∑​lg(f(k))=lg(f(m))根据公式4.56证明过程​
对该式去掉lg则有
Ψ m ( z ) = f ( m ) = ∏ d ∖ m ( ∏ k ∖ d f ( k ) ) μ ( m d ) = ∏ d ∖ m ( z d − 1 ) μ ( m d ) \begin{aligned} \displaystyle \Psi_m(z) =f(m)&=\prod_{d\setminus m}(\prod_{k\setminus d}f(k))^{\mu(\frac{m}{d})}\\ &= \prod_{d\setminus m}(z^d-1)^{\mu(\frac{m}{d})}\\ \end{aligned} Ψm​(z)=f(m)​=d∖m∏​(k∖d∏​f(k))μ(dm​)=d∖m∏​(zd−1)μ(dm​)​
原式得证

Problem 4 (20 points). Exercise 58 in Chapter 4

因为$g(x)=x$是积性的，根据所以公式4.54的后续推导可知 f ( m ) = ∑ d ∖ m d \displaystyle f(m)=\sum_{d \setminus m}d f(m)=d∖m∑​d也是积性的，m可以表示为 p 1 a 1 p 2 a 2 … … p n a n 的形式 , 其中 p 是素数 p_1^{a_1}p_2^{a_2}……p_n^{a_n}的形式,其中p是素数 p1a1​​p2a2​​……pnan​​的形式,其中p是素数，

1）考虑 m = p 1 a 1 m=p_1^{a_1} m=p1a1​​的情况，其他情况可以通过$f(m)$的积性相乘得到。

f ( m ) = ∑ d ∖ m d \displaystyle f(m)=\sum_{d \setminus m}d f(m)=d∖m∑​d，令 m = p k m=p^k m=pk,$p$为素数，则有

f ( m ) = 1 + p + p 2 + … … + p k f(m)=1+p+p^2+……+p^k f(m)=1+p+p2+……+pk,需要$f(m)$为2的幂，则p必须是奇数，同时有

a. $f(m)$为偶数项叠加，k为奇数

b. k = 2 t − 1 k=2^t-1 k=2t−1的形式

$f(m)$可改写成 ( 1 + p ) ( 1 + p 2 ) … … ( 1 + p ( 2 t − 1 ) ) (1+p)(1+p^2)……(1+p^{(2^{t-1})}) (1+p)(1+p2)……(1+p(2t−1))的形式，这里一共是t项叠乘，由于$f(m)$是2的幂，因此每一项都需要是2的幂或1，设 1 + p = 2 x 1+p=2^x 1+p=2x,则 1 + p 2 = 1 + ( 2 x − 1 ) 2 = 2 2 x − 2 × 2 x + 2 = 2 ( 2 2 x − 1 − 2 x + 1 ) 1+p^2=1+(2^x-1)^2=2^{2x}-2\times2^x+2=2(2^{2x-1}-2^x+1) 1+p2=1+(2x−1)2=22x−2×2x+2=2(22x−1−2x+1)必然不是2的幂，因此k只能为1

c. k是奇数，但 k ≠ 2 t − 1 k≠2^t-1 k=2t−1

$f(m)$可以改写成 ( 1 + p ) ( 1 + p 2 ) … … ( 1 + p t 1 + p t 2 + … … ) (1+p)(1+p^2)……(1+p^{t1}+p^{t2}+……) (1+p)(1+p2)……(1+pt1+pt2+……)的形式，其中除了最后一项外，都是 1 + p x 1+p^x 1+px的形式，但因为$f(m)$叠加时项的个数不为2的幂，因此叠乘时最后一项 ( 1 + p t 1 + p t 2 + … … ) (1+p^{t1}+p^{t2}+……) (1+pt1+pt2+……)括号内必然是奇数项，所以此时$f(m)$不为2的幂

综上，$f(m)$为2的幂要求k必须为1

因此， f ( m ) = 1 + p = 2 x f(m)=1+p=2^x f(m)=1+p=2x,同时$p$为素数，因此$p$应当为梅森素数的形式，也就是m应为梅森素数。

又因为$f(m)$为积性函数，当 m 1 ⊥ m 2 m_1 \perp m_2 m1​⊥m2​时，有 f ( m 1 m 2 ) = f ( m 1 ) f ( m 2 ) f(m_1m_2)=f(m_1)f(m_2) f(m1​m2​)=f(m1​)f(m2​),因此m可以为多个不同梅森素数的乘积

∴ 充要条件为：m为多个不同梅森素数乘积

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！