离散数学基础-习题参考答案-第4章 初等数论基础

第4章初等数论基础

2第4章习题

4.1533.

4.2250.

4.3(1)不正确.反例:a=2,b=4,c=4.

(2)正确.因为a|c,6|d,所以存在整数瓦m使得c=ak.d=Imi.因此,cd=(ak)(bm)=ab(km),即

ab|cd.

(3)正确.若而|c,则存在整数1使得c=Qbk.因此,c=a(〃),即a|c.

(4)不正确.反例:Q=6,b=2,e=3.

4.4。当n是偶数时，设几=2k,其中k是非负整数，则有

3n+l=32fc+l=(3A)2+1.

由于3fc是一个奇数(因为奇数的任何正整数次累仍然是奇数)，设於=2m+1,其中m是整数.因此、

2

(3*)2+1=(2m+I)+1=2(2—+2m+1).

这表明3"+1能被2整除，但不能被4整除，因为2m2+2m.+1是一个奇数.因此，当n是偶数时,

2|3n+l.

。当n是奇数时，设〃=2卜+1,其中k是整数，则有

3n+1=32fc+1+l=3-32fc+l=3(3fc)2+l.

再次，由于3k是一个奇数，设3k=2m+1,其中m是整数.因此，

2

3•(3”产+1=3•(2m+1)+1=4(3/+3m+1).

这表明3n+1能被4整除，但不能被8整除，因为37川十3m+1是一个奇数.因此，当〃是奇数时，有

22|3n+l.

。从上述(1)(2)步骤中，我们看到当77.是偶数时，3"+1能被2整除但不能被4整除；当n是奇数时,

3"+1能被4整除但不能被8整除,这表明对任何m>23、1不能被整除.

4.5(存在性)当n=1时，可以表示为1=0・60+1,满足条件.假设对于任意14m<%存在k和rf使得m可

以表示为

m=r/++•••+ri6+r0.

考虑〃，存在唯一的整数Q和「使得

n=qb+r,0r<b.

由于q<〃,根据归纳假设,q可以表示为

q=rkbk~l+rk-\bk~2+…+rp

因此.有

n=qb4r=（叫心一】ii•••iir=i<•••»rtb

第4章习题

这表明n也可以表示为所需的形式.

（唯一性）设〃有两种不同的表示：

n=rkbk+rk-\bk~l+•••+r\b+TQ-sg"+Sk-i^kl+,,,+$ib+$o,

其中0（片,当•<6且「小Sk丰0.先比较最高位:如果A:学/,不妨设k>2,则

r/&ri<（以+1）泸.

由于sF的最大值为他-1）也因此

kk

SKb+S11心-1+...4-9[b+SoVbb=心+】,

这与九》小心矛盾，因此上=/.再逐位比较:对于A：=/，有

『kb"+?飞一曲"1+…+T\b+r（）=s^b"+i+…+S]b+s。.

两边同时除以bk并取整数部分，得

rk=Sk.

然后两边同时减去?讨,得

了h1胪-1+…+rib+ro=Sk-ibk~l+•••+61b+SQ.

重复上述过程，可以得到n-i=S-A：-],l'k-2-S"2,…，/0=«o-因此,〃的表示是唯一的.

4.6（存在性）根据带余除法，存在唯一的火/0£Z使得Q=（岫+r0,其中04厂。<跳下面调整余数如使其满

足一5（"I。

。如果「0=0,则『=0满足条件.

。如果0<r0<与，则r=ro已经满足条件.

O如果耳w%<冏，则令r==0-I"和<7=<7o+1.此时，r=r0-|6|<|fe|-|6|=0,且

『=「0一帆》学一回=一耳.

因此,-学一<0.

（唯一性）假设存在两组不同的q,r和，，/使得a=qb+r和a=q'b+/,其中一兴/<母和一袅/（母,

则有qb+r=/b+/.整理得（q-qr）b=r'e因此,|八r|=|q-/||b|.同时，由一号《r鸣和岑《<•

知，尸-「|<|6|.结合上述两个不等式，得\q-（ir\\b\<此故\q-q，\<1.由于q和/均是整数,薪以必须有

q=，.因此r=人这表明这种表示是唯一的.

4.7设I€IR,n是正整数,则根据带余除法,存在唯一的q,rwZ使得x=如+r,其中0<r<7）.设in=[xj,则

m<ar■<?n+1,BPzn<qn+r<in+1.由于04rvn,所以有m<qn+r<[q+l）n.

一方面，从m4qn+rnJ得TL-rqn.因为0r<n.所以m-rm-n+1.因此，m-〃+14,两边同

时除以心得-------<<7,即—-1+—q.因为q是整数且一W1,所以--《<?.

nnnnn

另一方面：由m4qn+r<m+1和0Wr<小得qn<m+1，两边同时除以n,有q<'+,即q《巴•

nLn

综上得，-«"，因此q=9.进而代回等式（*），由好-和根=[到得|±|=|©|.

nnnLnJLnJ[nJ

4.8（1）gcd（168,300）=12.

(2)lcm(168,300)=4200.

(3)gcd(120.504,882)=6.

第4章习题

(4)lcm(135,513,3114)=2-33•5•19•173=887490.

4.9(1)s=9,£=-5.

(2)s=-47?i=40.

4.10设fl=PilP?-Pkk'b=PilP22'-Pkk'c=P芸酸…成其中Pi是素数,勺,九%是非负整数(如果某个素数在

某个数的分解中不存在，则对应的指数为0),则

lcm(a,“C)=p,ax®L)p,ax(e2j23L.pEax(e*Jk®)

因为ab=PF+%产加“浮仁ac=p?+9ip产92...p浮叫阿=p£+gip尹"..pp+g*,所以

inin(fi+/*,e*+gJ+g；

gcd(QAQGbc)=*n(eM.+gi」心)niin(e2+/2^2+<72J2+J72)fckkk

P-2、l)k

而abc=琢+为+92…璟+G+g\

--fi1+/1+91^2+/；+ff2....y^k+fk+Hk

|a6c|Pl〃2Pk

gcd(gac,be)ptnin(ei+/i,ei+giJi+gi)p：nin(e2+/2,e2+g2J2+92)…pinin(ea+/*&+g*J*+g*)'

且对每个素因子Pi,

丁门+力+⑺

max(ejjj,gj

min(e4+A,et+gt,f{+gt)

〃i

因此,

|o.dc|

_inax(ei./1,jn),niax(e2J2,</2)inax(efc,/fc,Sfe)

-=lcm(a.6,c).

gcd(«6,ac,be)Pl〃2…〃A：

4.11（1）首先，由＜/=8。（1（0”）,根据最大公因数的性质,存在整数加和展使得4=。皿+加.如果d|c,则存在

整数k使得c=dk,因此,c=dk=（am+bn）k=a（mk）+b（nk）.令①=ink和g=nk,则i和9是方

程ax+勿=c的整数解，反过来,如果方程Qi+珈=c有整数解x和"，那么c可以表示为。和〃的

整数线性组合.由于d是Q和b的最大公因数，因此d必须整除c.

（2）由于d=gcd（Q,b）,我们可以将方程a；r+by=c两边同时除以d,得到

abc

1a7ay=7ct

显然，如果（*!/）是方程az+b“=c的解.那么它也是方程4a:+^V:彳的解.反之，如昊（了,必是方

CZ'U'C4

程2,+=；的解，那么它也是方程QC+如=c的解•

aaa

（3）设立=叼和y=?/o是方程1”•+by=c的一组特解.即ar（）+珈。=c.设1=N（）+%和%?/o-其

中t是任意整数.代入方程+如=C,得到

（b\/a\abba

a\XQ+dt）+br°一割=ax°+/+~~dt=aXCi+by（j=c

因此,c=&）+"和y=y0--t也是方程ax+by=c的解.

aa

反过来，假设①=叫和V=如是方程ax+by=c的任意解，即。①1+如i=c,则有

一的）+6（如-yo）=0.

由于d=gcd（Q,b）,可以将上式两边同时除以心得到

-①o）+3（2/1-沙。）=0.

da

设g-g=%和力-:如=-夕,其中f是整数，因此，任意解/=叫和y=?/i可以表示为

b,a-

x=x+-t,y=yo--t.

0a.a

4.12（1）£=-3U+73£,U=44-l（m,其中方为任意整数.

3

第4章习题

(2)x=-1704+19f,1/=639-7f,其中t为任意整数.

(3)^=-141+349t,j/=120-297t,其中t为任意整数.

(4)①=10+5331,y=-14-746t,其中t为任意整数.

4.13考虑a和b的素因子分解：Q=p7虎2..成,6=口夕〃3./3其中Pi、P2,…,Pk是素数,加和/；是非负整数

(若某个素数在a或b的分解中没有出现，则相应的指数为0),则有a?=?沪〃羿…〃泮庐=p"p沪…对〃

因为。2|根据整除的定义，对每个素数pi1中pj的指数必须小于或等于庐中p.的指数，即2&Y26,

亦即与《九对所有i=1,2,...,A：.这意味着a中每个索数的指数都小于或等于h中相应素数的指数，因此

a|b

126=2x32x7,

256=28,

4.141092=22x3x7x13,

6325=52x11x23,

20!=218x38x54x72x11x13x17x19.

4.15113,213-1是素数;221,527是合数.

4.16反证法.假设形如4n-1的素数只有有限多个，记作m,P2,…,Pg令N=4pim…PL4显然，N是形如

4/1-1的数，且N大于任何一个Pi.因为N是奇数，所以它的素因数只能是形如乐+1或g-1的素数.

如果N的所有素因数都是形如4"+1的素数，那么N本身也应该是形如4?1+1的数(因为形如4/7+1的

数的乘积仍然是形如4〃+1的数)，故N至少有一个形如4n-l的素因数.设p是N的一个形如4n-l

的素因数.由于Pi,p2,…、Pk是所有形如4n-1的素数，因此p必须等于某个Pi.但N=4pip2…PkT,所

以P不能整除N(因为p整除4〃1理,"小但不整除-1),这与p是N的素因数矛盾.

4.17因为任何整数可以表示为6论,6Q+l,6k+2,6k+3,6A;+4,6k+5中的一个，而6fc,6fc+2,6fc+4是偶数,6k+3

是3的倍数，所以它们都不是素数(除了2和3),故任何大于3的素数p必须是形如6k土1的数，其中k

是正整数.

。若p=6k+1,则有2p+l=2(6fc+l)+l=12fc+3=3(4*+1),这表明2p+1不是素数.

。若.=6比-1,则有42+1=4(6k-1)+1=241-3=3(8卜-1)，这表明劭+1不是素数.

综上，对任何素数P>3,2p+1和4p+l不能同时为素数.

4.18(1)不成立.⑵不成立.(3)成立.(4)成立.

4.19⑴可利用ac-加=(a-，)c和定义证明.

(2)可利用(a+c)-(b+d)=(Q-6)+(c-d)和定义证明.

(3)可利用Qc-bd=(a-b)c+b(c—d)和定义证明.

(4)可利用an-bn=(a-b)^-1+an-26+an-362+-+a6n-2+571-1)和定义证明.

4.20(1)不正确，反例：a=3,6=l,m=8.

(2)正确.^1Jga2-b2=(a-b)(a+b).

(3)不正确,反例：a=5,6=4,m=3.

(4)正确.由定义显然成立.

(5)不正确，反例止=4,b=2,m=2,n=2.

4.21⑴不正确.反例:[Q卜⑵.

⑵正确.

⑶不正确.反例:田=[2],向=[3].

(4)正确.

第4章习题

4.22见表4.0」和表4.0.2.

表4.0.1:加法表表4.0.2:乘法表

㊉[0][1][2][3][4]⑸[0][1][2][3][4][5]

[0][0][1][2][3][4][5][0][0][0][0][0][0][0]

[1][1][2][3][4]⑸[0][1][0][1][2][3][4][5]

⑵[2][3][4]⑸[0][1][2][0][2][4][0][2][4]

[3][3][4]⑸[0][1][2][3][0][3][0][3][0][3]

[4][5][0][1][2][3][4][0][4][2][0][4][2]

⑸[5][0][1]⑵[3]W[5][0][5][4]⑶[2][1]

4.23根据费马小定理，得2'5-1=24=1(mod5),HP24=1(mod5).进而有2“=(2，"=1/'=1(mod5),因此,

2umod5的最小非负余数是1.

4.24将n表示为n-。卜•10比+a，k-\-10fe-1+…+函•10+GQ.由于10=-1(mod11),有

10,三(-1)?(mod11)对于所有整数i.

因此，可以将联模11表示为

n=ak•(-1)^+ajt-i•+•••+a】•(-1)+a()(mod11),

即

n=ao-ai+a2-。3++(-1)kQk(mod11).

因此，111n当且仅当111(«o-«i+。2-。3+…+(T)%Q・

4.25设/Q)是一个整系数多项式，可表示为/(⑼=斯廿+。时途'1+…+。途+旬,其中%是整数.则有

(/(%))，=仕%，).

\i=0!

对每个单项式2有(QRV=Q?C?)".由处是整数，根据费马小定理，有

a,三Qi(modp).

因此

(aH)P=(modp).

考虑(/(①)),的展开中的每一项

加「

Y…':愁中…a*/+2A"・+%

机+品£+b”&：o!ki!-kn!

当〃>1时，一包含因子P(除非某个权=p),因此这些系数模p都为0；唯一剩二的项是那些

尢=〃或自=0的项：(1)信=〃且所有其他为=0;(2)所有后=0(即常数项).因此,展开化简为

pnpn-1p

(/(a?)),,=an(x)+an-i(®)+•••+«i(x)+«o(modp),

这正是

")=(*P)"T+…+⑸(*+a0.

综上,证明了三f(xp)(modp).

4.26对任意整数-我们分析x对所有模数的可能余数.

第4章习题

先考虑模2的情况：1对模2的余数只能是。或1,即

二三0(mod2)或x=l(mod2).

如果，三0(mod2),那么①满足第一个同余式.否则，①三1(mod2),此时考虑1对模3的余数：

,三0(mod3),x=l(mod3),或x=2(mod3).

若一三0(mod3),则x满足第二个同余式.若£杀0(mod2)且①羊0(mod3),则上三1(mod2)且］三1

(mod3)或二三2(mod3).考虑x对模4的余数：

①三0(mod4),①三1(mod4),二三2(mod4),或①三3(mod4).

如果x=1(mod4),那么x满足第三个同余式.如果c杀0(mod2)、i±0(mod3)且①杀1(mod4),那

么〜三1(mod2)、/三2(mod3)且x=3(mod4).考虑x对模6的余数:

3：=0(mod6),3：=1(ir.od6),a;=2(mod6),1：=3(mod6),二三4(mod6),或工三5(mod6).

如果c三5(mod6),那么x满足第四个同余式.如果/杀0(mod2)、c杀0(mod3)、①誉1(mod4)且

一千5(mod6),那么x=1(mod2)、工三2(mod3)、一三3(mod4)且。三1(mod6).考虑x对模12的余

数：

r=7(mod12).

因此也满足第五个同余式.综上，任意整数,至少满足五个同余式中的一个.

4.27直接由定义可证.

4.28(必要性)由于S是模m的完全剩余系，它必须包含每个可能的余数0,1,2一・,加-1恰好一次，这意味着S

中有m个不同的元素.即A：=m.此外，因为每个余数0,1,2,…,1在S中恰好出现一次.所以当itj

时,a"(ij(modm).

(充分性)设S满足以下条件：

(1)k=m\

(2)当itj时，Q"aj(modm).

由于S包含m个元素，且任意两个元素模m不同余，因此S中的元素恰好覆盖了模m的所有剩余类.另

外，对任意整数凡存在唯一的修eS使得x=%(modm),因此,S是模m的完全剩余系.

4.29可以利用习题4.28来证.

(1)由于S=｛ai,Q2,…,Q”J是模m的一个完全剩余系，它包含m个不同的整数，因此集合S=｛kaA+

b,ka-2+b,…,kam+b｝也包含m个元素.

(2)当，羊1•时，我们需要证明kai+b^kaj+b(modm).这等价于证明ka,*kcij(modm).因为k与m

互素：即gcd(hm)=1，所以一在模rn下有逆元A:-1.因此：若=kaj(mndin),则可以两边同时

乘以A-(也可以由习题4.27(2))得到Qi三QJ(modm),但是这与S是模m的完全剩余系矛盾.因

此，必有kaikaj(modm).

4.30由于m是偶数，设in=2Ar.因为和｛3如…％｝都是模m的完全剩余系，所以有

》三七bj=-------------=-1)(modm).

：=ii=i2

从而

rnmm

X(&+加)=£%+XA三三-1)+Ar(m-1)=2k(m-1)=0(modm).

:=1i=li=l

第4章习题

若｛的+3。2+瓯…,Qm+%｝是模m的完全剩余系，则其和应满足

2(Q1+仇)三血("：__12=-1)(modm).

i=i2

由此得到k(m-1)=0(modm)，即k=0(modm),矛盾.因此｛QI+力,。2+风+bm｝不是模m的

完全剩余系.

4.31由定义显然成立.

4.32(i)由于S中有0(m)个元素，而S'是通过将5中的每个元素乘以与m互索的整数k得到的，因此夕

中也有个元素.

(ii)假设S'中存在两个元素ka.i和眄(刀，)满足kai=kaj(modm),则由于gcd(fc,m)=lyk在模m

下有乘法逆元『,因此两边同时乘以F1,得到修=町(modm),这与S是既约剩余系的条件矛

盾，故£中的任意两个元素模m不同余.

(iii)对于S'中的任意元素栖，由于gcd(k,m)=1且gcd(%m)=1(因为佻eS),可得gcd-Mm)=1,

因此.S'中的每个元素都与m互素.

由习题4.31知,S'也是模m的规约剩余系.

4.33(1)对索数p和整数Q》1,考虑不大于严且与？产互素的正整数的个数.由于P是索数，因此一个数x

不大于pa且与P。不互素当且仅当，是〃的倍数.而在1,2,…,p°中，有〃"一】个数是p的倍数(即

p,2p,…,pa-】p),剩下的数都与互素,总数为Pa-Pa-1.于是得到此巧=浮-P°T.

(2)考虑所有不大于ab且与ab互素的正整数.根据中国剩余定理，每个这样的整数x对应于一对

其中g是不大于Q且与«互素的正整数，3是不大于b且与b互素的正整数，并且满

足以下同余方程组：

x=xa(moda),

x=(mod6).

因为。和b互索，上述同余方程组对每一对(%,g)都有唯一解.因此,不大于ab且与ab互素的正

整数的个数等于不大于。且与。互索的正整数的个数乘以不大于b且与b互素的正整数的个数，即

0(ab)=-b).

4.34根据习题4.33中欧拉函数的性质(2).我们有

0(m)=0(p『M(p-)W(p产).

应用欧拉函数的性质(1),我们可以计算每个)：

机P;)=P；-pfT=P7(l-L).

Pi

因此，

k卜[

e(m)-n。(靖)-

i«li«lPi

注意至IJm=P『PP『，我们将上述等式改写为

&•i

(p(m)=?7?n(1—)，

i=TPi

即

4.35(1)m=3,7,21.

(2)m=11.