注:本节内容为《具体数学》(原书第二版) 第四章 数论 热身题的答案。

4.1

4.2

(1)

k=gcd(m,n)kp=min(mp,np)

k=lcm(m,n)kp=max(mp,np)

k=gcd(m,n)lcm(m,n)kp=min(mp,np)max(mp,np)=mpnp

gcd(m,n)lcm(m,n)=mn

(2)

注意到

gcd(m,n)=gcd(nmodm,m)

gcd(m,n)lcm(m,n)=mn

gcd(nmodm,m)lcm(nmodm,m)=(nmodm)m

联立等式得

lcm(m,n)=nlcm(nmodm,m)nmodm

4.3

见答案

4.4

具体考察三种差异:

  1. 方向相反
  2. 分子取负
  3. 分母取负

4.5

由归纳可证:

Lk=(1k01)

Rk=(10k1)

repo 中的 code/ch4/4.5.cpp 为验证代码。

4.6

ab(mod0)a=b

因为

amod0=a

4.7

根据我在第一章练习题 1.21 中定义的新记号,如果三个死者的编号分别为 10,k,k+1,我们有

m10=10

(10+m1)9=k

(k+m1)8=(k+1)1

注意:最后一个等式之所以为 (k+1)1 是因为正如我们习题 1.21 的解法一样,我们规定了死者编号顺延机制。

经过化简可得:

m10=10m0(mod10)

(m1)8=8m10(mod8)

根据上一个式子,m 为偶数,为 10 的倍数,而下面一个式子则暗示了 m 为奇数。矛盾。

4.8

10x+yx(mod3)

10x+yy(mod5)

经过化简可得第二个同余式恒成立,第一个式子转化为

y0(mod3)

所以

x=0,1

y0(mod3)

4.9

证明奇数非常容易,因为:

3mod4=3

32mod4=1

由同余乘法法则,

377mod4=3

不难证明:

377121(mod2)

接下来,我们找其的一个因数来证明其是合数。

不难得到:

37712=(31)(376+375++30)2=376+375++30=(30+31+311)(1+311+322++366)

4.10

999=33×37

根据公式

φ(999)=999×(113)×(1137)=648

4.11

莫比乌斯函数:

dmμ(d)=[m=1]

类推:

0knσ(k)=[n=0]

不难得出这个函数的通项:

σ(n)={1n=01n=10n>1

接下来我们来验证性质。

g(n)=0knf(k),则

0knσ(k)g(nk)=0knσ(nk)g(k)=0knσ(nk)0jkf(j)=n1knσ(nk)0jkf(j)=0jnf(j)+(1)0jn1f(j)=f(n)

f(n)=0knσ(k)g(nk),则

f(n)={g(n)g(n1)n1g(0)n=0

0knf(k)=g(n)

Q.E.D.

4.12

已在 μ 函数的旁注一文中解答。

4.13

(a)

np<2,ppnp=n

(b)

μ(n)0

最后修改:2022 年 03 月 13 日 02 : 56 PM
真的不买杯奶茶嘛....qwq