首页
登录 | 注册

具体数学第二版第四章习题(4)

46 (1)假设$j^{'}j-k^{'}k=Gcd(j,k)$,那么有$n^{j^{'}j}=n^{k^{'}k}n^{Gcd(j,k)}$,所以如果$n^{j^{'}j}=pm+1,n^{k^{'}k}=qm+1\rightarrow n^{Gcd(j,k)}=rm+1$

(2)假设$n=pq$并且$p$是$n$的最小素因子(如果$n$为素数那么$p=n$)。所以$2^{p-1}\equiv 1(mod(p))$。如果$2^{n}\equiv 1(mod(n))\rightarrow 2^{n}\equiv 1(mod(p))$。所以根据上面一个小题的结论,$2^{Gcd(p-1,n)}\equiv 1(mod(p))$。而由于$p$是$n$的最小素因子,所以$Gcd(p-1,n)=1$。这会导致错误。所以$2^{n}\not\equiv 1(mod(n))$

47 $n^{m-1}\equiv 1(mod(m))\rightarrow n\perp m\rightarrow n^{t}\perp m\rightarrow \left ((n^{t})mod(m)  \right )\perp m,1\leq t <m$

假设:如果对于所有的$1\leq t <m$,$\left (n^{t}  \right )mod(m)$不是各不相同的,比如对$1\leq x < y < m$有$\left ((n^{x})mod(m)  \right )=\left ((n^{y})mod(m)  \right )$,那么$n^{y-x}\equiv 1(mod(m))$,其中$y-x<m-1$

根据题目46第一小题的结论,$n^{y-x}\equiv 1,n^{m-1}\equiv 1\rightarrow n^{Gcd(y-x,m-1)}\equiv 1$,而$Gcd(y-x,m-1)<m-1$,所以存在一个素数$p$以及一个整数$q$满足$(y-x)q=\frac{m-1}{p}$,而$\left ( n^{\frac{m-1}{p}}=n^{(y-x)q} \right )\equiv 1$,而这与题目给出的$n^{\frac{m-1}{p}}\not\equiv 1$矛盾了。所以上面的假设错误。

对于所有的$1\leq t <m$,$\left (n^{t}  \right )mod(m)$各不相同,并且都与$m$互质,所以$1,2,3,...,m-1$都与$m$互质,所以$m$是素数

48 将每个数字与其逆元相乘,可以不管这些,那么只剩下那些逆元是自己的数字,所以就是计算$\prod_{1\leq n < m,(n^{2})mod(m)=1}n$.根据$n^{2}\equiv 1(mod(m))$的解可以得到,当$m=4,p^{k},2p^{k}(p>2,k\geq 1)$答案为-1,否则为1

49 (1)首先考虑$m<n$,此时答案为$\Phi (N)=\left (\sum_{k=1}^{N}\varphi (k)  \right )-1$,$m>n$也是这个,$m=n$时只有$m=n=1$成立,所以答案为$R(N)=2\Phi (N)-1$

(2)由公式4.62可以得到$R(N)=2\Phi (N)-1=-1+\sum_{d\geq 1}\mu (d)\left \lfloor \frac{N}{d} \right \rfloor\left \lfloor \frac{N}{d}+1 \right \rfloor=\sum_{d\geq 1}\mu (d)\left \lfloor \frac{N}{d} \right \rfloor^{2}+\left (\sum_{d\geq 1}\mu (d)\left \lfloor \frac{N}{d} \right \rfloor-1  \right )$

所以现在只需要满足$\sum_{d\geq 1}\mu (d)\left \lfloor \frac{N}{d} \right \rfloor=1$即可

在公式4.61中,令$f(x)=[x\geq 1]\rightarrow g(N)=\sum_{d\geq 1}[\frac{N}{d}\geq 1]=N\rightarrow \sum_{d\geq 1}\mu (d)\left \lfloor \frac{N}{d} \right \rfloor=\sum_{d\geq 1}\mu (d)g(\left \lfloor \frac{N}{d} \right \rfloor)=\sum _{d\geq 1}\mu (d)g(\frac{N}{d})=f(N)=1$

50 (1) 设$f$是任意一个函数。$\prod_{0\leq k < m}f(k)=\prod_{d|m}\prod_{0\leq k < m}f(k)[d=Gcd(k,m)]=\prod_{d|m}\prod_{0\leq k < m}f(k)[\frac{k}{d}\perp \frac{m}{d}]=\prod_{d|m}\prod_{0\leq k < \frac{m}{d}}f(kd)[k\perp \frac{m}{d}]=\prod_{d|m}\prod_{0\leq k < d}f(k\frac{m}{d})[k\perp d]$

所以$z^{m}-1=\prod_{0\leq k < m}(z-\omega ^{k})=\prod_{d|m}\prod_{0\leq k < d,k\perp d}(z-\omega ^{\frac{km}{d}})=\prod_{d|m}\Psi _{m}(z)$

最后一步成立是因为$\omega^{\frac{km}{d}}=e^{\frac{2\pi i}{m}*\frac{km}{d}}=e^{\frac{2\pi i}{d}*k}$

(2)如果令$g(m)=z^{m}-1,f(m)=\Psi _{m}(z)$,也就是已知$g_{m}=\prod_{d|m}f(d)$而证明$f_{m}=\prod_{d|m}g(d)^{\mu (\frac{m}{d})}$,两边都取对数,就变成了公式4.56

51 $(x_{1}+x_{2}+...+x_{n})^{p}=\sum_{k_{1}+k_{2}+..+k_{n}=p,k_{i}\geq 0}\frac{p!}{k_{1}!k_{2}!..k_{n}!}x_{1}^{k_{1}}x_{2}^{k_{2}}..x_{n}^{k_{n}}$

如果所有的$k_{i}<p$,那么$\frac{p!}{k_{1}!k_{2}!..k_{n}!}x_{1}^{k_{1}}x_{2}^{k_{2}}..x_{n}^{k_{n}}\equiv 0(mod(p))$

所以$(x_{1}+x_{2}+...+x_{n})^{p}\equiv x_{1}^{p}+x_{2}^{p}+..+x_{n}^{p}(mod(p))$。因此当$x_{i}=1$时有$n^{p}\equiv n(mod(p))$

52 如果$p>n$则一定成立。

如果$p\leq n$,那么$p\perp x\rightarrow x^{p-1}\equiv 1(mod(p))\rightarrow x^{k(p-1)}\equiv 1(mod(p))$

所以只要计算$[1,n-1]$中有多少个数字是$p-1$的倍数即可。有$\left \lfloor \frac{n-1}{p-1} \right \rfloor$个。而由于$p\leq n\rightharpoonup \frac{n-1}{p-1}\geq \frac{n}{p}$

53 如果$m\geq 6$并且$m$是合数,那么$(m-2)!\equiv 0(mod(m))$

(1)如果$n<5$,只有$n=1$满足

(2)如果$n\geq 5$,并且$n$是素数,由于$(n-1)!$没有素数$n$,所以$n$不可能整除$\frac{(n-1)!}{n+1}$

(3)如果$n\geq 5$,并且$n$是合数,并且$n+1$也是合数,那么$n$和$n+1$都可以整除$(n-1)!$,并且由于$n\perp (n+1)$,所以$n(n+1)$可以整除$(n-1)!$
(4)如果$n\geq 5$,并且$n$是合数,并且$n+1$是素数,那么由威尔逊定理$n!\equiv -1(mod(n+1))\rightarrow (n-1)!\equiv 1(mod(n+1))$,所以$\left \lceil \frac{(n-1)!}{n+1} \right \rceil=\frac{(n-1)!+n}{n+1}$。而$(n-1)!\equiv 0(mod(n))$, 所以$(n-1)!+n$是$n$的倍数,而且$n$和$n+1$互质,所以$n$可以整除$\frac{(n-1)!+n}{n+1}$

所以$n=1$或者$n$是大于5的合数

54 $\epsilon _{2}(1000!)>500,\epsilon _{5}(1000!)=249$,因此存在一个偶数$a$满足$1000!=a*10^{249}$

$1000=(13000)_{5}$ ,那么由第40题的结论可以得到$\left (a*2^{249}=\frac{1000!}{5^{249}}  \right )\equiv -1(mod(5))$

另外有$2^{249}\equiv 2(mod(5))\rightarrow a\equiv 2(mod(5))$,所以$a=10k+2$或者$a=10k+7$

如果$a=10k+2$,那么$\left (1000!=a*10^{249}=(10k+2)*10^{249}  \right )=2*10^{249}(mod(10^{250}))$

如果$a=10k+7$,答案也是这个

55 考虑每个素数$p$在$P_{2n},P_{n}^{4}$中出现的次数。那么只需要对于所有的$t\geq 1,p\geq 2\rightarrow \sum_{k=1}^{2n}\left \lfloor \frac{k}{p^{t}} \right \rfloor\geq 4\sum_{k=1}^{n}\left \lfloor \frac{k}{p^{t}} \right \rfloor\rightarrow\sum_{k=1}^{2n}\left \lfloor \frac{k}{m} \right \rfloor\geq 4\sum_{k=1}^{n}\left \lfloor \frac{k}{m} \right \rfloor,m\geq 2$

首先,证明下面的公式成立$\left \lfloor \frac{2n-1}{m} \right \rfloor+\left \lfloor \frac{2n}{m} \right \rfloor\geq 4\left \lfloor \frac{n}{m} \right \rfloor+[n\equiv m-1(mod(m))]-[n\equiv 0(mod(m))]$

首先,当$1\leq n \leq m$是成立。其次,当$n$每增加$m$,两边都同时增加4。所以成立。

然后将$n$取$1,2,3,...,n$的所有式子加起来,最后只需要证明$\sum_{k=1}^{n}[k\equiv m-1(mod(m))]=\sum_{k=1}^{n}[k\equiv 0(mod(m))]$即可。左边等于$\left \lfloor \frac{n+1}{m} \right \rfloor$,右边等于$\left \lfloor \frac{n}{m} \right \rfloor$。所以除了$n=tm-1$外,其他的$n$都成立。

而当$n=tm-1$时可以得到$4\sum_{k=1}^{n}\left \lfloor \frac{k}{m} \right \rfloor=2t(t-1)m$,$\sum_{k=1}^{2n}\left \lfloor \frac{k}{m} \right \rfloor=t(2t-1)m-(2t-1)$

由$t(2t-1)m-(2t-1)-2t(t-1)m=km-2k+1\geq 1$

所以$\sum_{k=1}^{2n}\left \lfloor \frac{k}{m} \right \rfloor\geq 4\sum_{k=1}^{n}\left \lfloor \frac{k}{m} \right \rfloor,m\geq 2$恒成立

56 设$f(m)=\sum_{k=1}^{2n-1}min(k,2n-k)[m|k],g(m)=\sum_{k=1}^{n-1}(2n-2k-1)[m|(2k+1)]$

那么对于质数$p$来说,在分子分母中出现的次数分别为$\sum_{k\geq 1}f(p^{k}),\sum_{k\geq 1}g(p^{k})$。可以证明只要$m$为奇数,那么有$f(m)=g(m)\rightarrow \sum_{k\geq 1}^{p^{k}}f(p^{k})=\sum_{k\geq 1}^{p^{k}}g(p^{k})$,那么就得到所有不是2的质数都会被消去,所以只剩下2了。

下面证明只要$m$为奇数,那么$f(m)=g(m)$

可以分两种情况,第一种$2km\leq n < (2k+1)m$,第二种$(2k+1)m\leq n < (2k+2)m$

第一种情况: $2km\leq n < (2k+1)m\rightarrow 4km\leq 2n < 2(2k+1)m\rightarrow 4k\leq \left \lfloor \frac{2n}{m} \right \rfloor<4k+2$,所以$\left \lfloor \frac{2n}{m} \right \rfloor$等于$4k$或者$4k+1$。当它为$4k$时,$f(m)=g(m)=4kn-4k^2$;当它为$4k+1$时,$f(m)=g(m)=2k(2k+1)n-(2k+1)^2$

第二种情况计算方法类似

57 令$g(n)=\sum_{1\leq m \leq n}\sum _{d|m}\varphi (d)=\sum_{d\geq 1}\varphi (d)\left \lfloor \frac{n}{d} \right \rfloor$

那么$g(m+n)-g(m)-g(n)=\sum_{d\geq 1}\varphi (d)(\left \lfloor \frac{n+m}{d} \right \rfloor-\left \lfloor \frac{n}{d} \right \rfloor-\left \lfloor \frac{m}{d} \right \rfloor)=\sum_{d\in S(n,m)}\varphi (d)$

另外,由公式4.54可以得到$g(n)=\sum_{1\leq m \leq n}\sum _{d|m}\varphi (d)=\sum_{1\leq m \leq n}m=\frac{n(n+1)}{2}$

所以$g(m+n)-g(m)-g(n)=mn$

58 首先$f(m)$是积性的,也就是说$m=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{t}^{a_{t}}\rightarrow f(m)=\prod_{k=1}^{t}(\sum_{r=0}^{a_{k}}p_{k}^{r})$.所以每个因子都必须是2的幂。所以可以假设$m=p^{k}$

这时候$f(m)=1+p+p^{2}+..+p^{k}$。首先$k$必须为奇数并且$p$不是2.可以证明$k$只能等于1且$p$为梅森素数

假设$k=3\rightarrow f(m)=(1+p)(1+p^{2})$.如果$1+p$为2的幂,假设$1+p=2^{x}$那么$1+p^{2}=2^{2x}-2^{x+1}+2=2(2^{2x-1}-2^{x}+1)$不可能为2的幂。$k$为其他奇数类似。

所以$m$只能为若干梅森素数的乘积

59 证明那个更强的结果。

首先取$1$的时候,有$x_{1}=\alpha=2\rightarrow \alpha+1\leq e_{2},x_{1}(\alpha+1) \leq e_{1}e_{2}$

假设取$[1,n-1]$时均满足

当取$n$的时候,假设$x_{1}\leq x_{2}\leq .. \leq x_{n-1}\leq x_{n}$。分三种情况:

(1)$\frac{1}{x_{1}}+\frac{1}{x_{2}}+..+\frac{1}{x_{n-1}}+\frac{1}{x_{n}-1}\geq 1,x_{n}>x_{n-1}$,这时候一定存在$\beta \geq x_{n}-1\geq x_{n-1}\rightarrow \beta^{-1}+\sum_{i=1}^{n-1}x_{i}^{-1}=1$,所以$x_{n}\leq \beta+1\leq e_{n}\rightarrow x_{1}x_{2}...x_{n-1}x_{n}\leq  x_{1}x_{2}...x_{n-1}(\beta+1)\leq e_{1}e_{2}...e_{n-1}e_{n}$.另外如果$\alpha^{-1}+\sum_{i=1}^{n}x_{i}^{-1}=1\rightarrow \alpha=\frac{x_{1}x_{2}...x_{n}}{m}$,其中$m$为正整数,所以$\alpha\leq x_{1}x_{2}...x_{n}\leq e_{1}e_{2}..e_{n}=e_{n+1}-1\rightarrow \alpha + 1\leq e_{n+1}\rightarrow x_{1}x_{2}...x_{n}(\alpha+1)\leq e_{1}e_{2}...e_{n}e_{n+1}$

(2)$\frac{1}{x_{1}}+\frac{1}{x_{2}}+..+\frac{1}{x_{n-1}}+\frac{1}{x_{n}-1}\geq 1,x_{n}=x_{n-1}$,令$a=x_{n}\geq 4,a^{-1}+(a-1)^{-1}=(a-2)^{-1}+\zeta ^{-1}\rightarrow (a-2)(\zeta +1)\geq a^{2}$.存在$\beta \geq \zeta\rightarrow x_{1}^{-1}+..+x_{n-2}^{-1}+(a-2)^{-1}+\beta^{-1}=1\rightarrow x_{1}x_{2}..x_{n}\leq x_{1}x_{2}..x_{n-2}(a-2)(\zeta +1)\leq x_{1}x_{2}..x_{n-2}(a-2)(\beta +1)\leq e_{1}e_{2}..e_{n}$.这样剩下的证明跟(1)一样

(3)$\frac{1}{x_{1}}+\frac{1}{x_{2}}+..+\frac{1}{x_{n-1}}+\frac{1}{x_{n}-1}< 1$.令$a=x_{n},a^{-1}+\alpha^{-1}=(a-1)^{-1}+\beta^{-1}\rightarrow (a-1)(\beta+1)>a(\alpha+1)$,所以可以用$a-1,\beta$来代替$x_{n},\alpha$直到(1)或者(2)满足。因为这个操作后,重新排列$x_{i}$后会使得$x_{n}$变小。

60 生成一个素数序列$p_{1},p_{2},..,p_{n-1},p_{n}$,满足$p_{n}\geq p_{n-1}^{3}$并且$p_{n}$最小。可以证明如果$p_{1}$足够大,那么在$[p_{n-1}^{3},(p_{n-1}+1)^{3})$一定存在一个素数。否则,由题目给出的定理可以得到存在$p<p_{n-1}^{3}\rightarrow p+p^{\theta}\geq (p_{n-1}+1)^{3}\geq (p^{\frac{1}{3}}+1)^{3}\rightarrow p^{\theta}\geq 3p^{\frac{2}{3}}+3p^{\frac{1}{3}}+1$,但是如果$\frac{6}{11}<\theta<\frac{2}{3}$且$p$足够大,这种情况就不会出现。所以一定存在$p_{n}$满足$p_{n-1}^{3}\leq p_{n}<(p_{n-1}+1)^{3}$

令$a_{n}=3^{-n}ln(p_{n}),b_{n}=3^{-n}ln(p_{n}+1)\rightarrow a_{n-1}\leq a_{n}<b_{n}\leq b_{n-1}\rightarrow P=lim_{n\rightarrow oo}e^{a_{n}}$


相关文章

  • 代码审查作业
    代码审查 我对结对同伴的代码进行了审查,他的有关括号匹配的代码 审查结果 功能模块名称 括号匹配问题 审查人 牛斌帅 审查日期 2019年4月25日 代码名称 括号匹配问题 代码作者 房旭 文件结构 重要性 审查项 结论 头文件和定义文件的 ...
  • 如何零基础开始自学Python编程
    转载——原作者:赛门喵 链接:https://www.zhihu.com/question/29138020/answer/141170242 0. 明确目标 我是真正零基础开始学Python的,从一开始的一窍不通,到3个月后成功搭建了一个 ...
  • 人性的弱点读书笔记   这是我第二遍读<人性的弱点>这本世界励志圣经,里面讲的很多东西到现在仍然很有实用价值,如果只是单纯的把它当做一本成功学的书籍,是比较比较浅薄的理解.人生于世,复杂而美妙,我们队我们自己的研究,对人性的探讨 ...
  • 之前自己一直想总结一下国内搞机器学习和数据挖掘的大牛,但是自己太懒了.所以没搞...最近看到了下面转载的这篇博文,感觉总结的比较全面了.个人认为,但从整体研究实力来说,机器学习和数据挖掘方向国内最强的地方还是在MSRA,那边的相关研究小组太 ...
  • AI历史和哲学基础浅谈
    换个角度看AI:研究历史和哲学逻辑 正如题图所示,仿生人会梦见电子羊吗?(注:Do Androids Dream of Electric Sheep?是Philip K. Dick所著的一本科幻小说,讲述人类在一个崩坏的环境中复制自己并奴役 ...
  • 这一章应该算是比价了理论的一章,我有些概率论基础,不过起初有些地方还是没看多大懂.其中有些公式的定义和模型误差的推导应该还是很眼熟的,就是之前在概率论课上提过的,不过有些模糊了,当时课上学得比较浅. Day2 第二章 模型评估与选择 2.1 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.076 s.
京ICP备10005923号