《初等数论闵嗣鹤、严士健》第三版习题解答

第一章整数的可除性

§1整除的概念•带余除法

1.证明定理3

定理3假设%,%…，%都是加得倍数，%%，…，%是任意〃个整数，那

么qxa[+q2a2+…+是m得倍数.

证明：：4,生…,4都是加的倍数。

存在"个整数P1,。2,…P"使%=PM，%=P2机，…，an=Pnm

又如名，…应”是任意〃个整数

•••4M+42a2+…+q”a”

=%p}m+q2p2m+---+qnpnm

=(〃UI+%P2+・..+ZP“)M

即q、a}+42a2+…+<7,4是阳的整数

2.证明3|/?(/?+1)(2/?+1)

证明n{n+1)(2〃+1)=n(n+1)(〃+2+〃-1)

=〃(〃+1)(〃+2)+(〃-1)〃(〃+1)

又〃(n+1)(〃+2),(n-1)〃(〃+2)是连续的三个整数

故3|”(〃+1)(〃+2),3|(〃一1)〃(〃+1)

3|”(〃+1)(〃+2)+(”-1)〃(”+1)

从而可知31”(〃+1)(2”+1)

3.假设以。+力。是形如依+勿(x,y是任意整数，a,b是两不全为零的整数)的数中最

小整数，那么(以0+0%)|(ax+by).

证：•.•。力不全为0

在整数集合S={ax+by\x,y&Z}中存在正整数，因而有形如ax+by的最小整数

5+by。

Vx,yGZ,由带余除法有ax+by=(ax0+by0)q+r,0<r<ax0+by0

那么r-(x-x(}q)a+(y-yoq)beS,由ox。+by()是S中的最小整数知

axQ+by0\ax+by

・.•％+〃％\ax+by(为任意整数)or。+〃为\a,ax()+byQ\h

:.ax0+byQ又有(a,b)|a(a,b)\b

(a,b)|ax0+by。故〃x()+by。=(a,b)

4.假设a,b是任意二整数，且bwO,证明：存在两个整数s,t使得

a=bs+t,111<—

2

成立，并且当b是奇数时，s,t是唯一存在的.当b是偶数时结果如何？

证：作序列…,--卜,-网,-■],0,wJW，-,…那么4必在此序列的某两项之间

即存在一个整数“，使£网<”等网成立

⑴当4为偶数时，假设b>0.那么令5=]/=。—芯=。—葭人，那么有

OKa-加=r==<£网川<耳

假设匕<0那么令s=/,f=a—加=。+汐那么同样有卜|<耳

(花)当q为奇数时，假设匕>0那么令5=券/="一切=a—等b,那么有

一卜—一等』一等咏0.用雪

假设b<0,那么令s=—4=。+怨人，那么同样有综上所述,

存在性得证.

下证唯一性

当b为奇数时，设"加+/=如+4那么卜一号|=-s)|〉\b\

而M碧,间省.,.”寸州+川明矛盾故s="=4

当。为偶数时，sj不唯一，举例如下：此时g为整数

cb-b1C，b、biih

3'2=b'i+2=b'2+(~2)，t'=2'^~2

§2最大公因数与辗转相除法

推论4.1a,6的公因数与(a,b)的因数相同.

证：设，是a,b的任一公因数，二/|a,d'|b

由带余除法

a=bq}+rvb

=他+弓,…，*2

0=乙+1<£<4T<..•<{<〃

(a,b)=rn

d'\a-bqx=rt,d'\b-rtq2=r2,d'\rn_2=rn_xqn+rn={a,b'),

即d'是(a,b)的因数。

反过来(a,b)|a且(a,b)|b,假设力|(a,b\那么d"|a,d"g,所以(a,b)的因数都是a,。的

公因数，从而a,b的公因数与(。,加的因数相同。

2.证明：见本书P2,P3第3题证明。

3.应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求

法及辗转相除法实际算出(76501,9719).

解：有§1习题4知：

\/a,bGZ,b^0,Bs,tG2,使。=加+人|7区《。，

,使)=卬+4，情区,4掾,…,如此类推知:

击〃，*乙_2=。-品+%

外"+I，。+1，=乙$"+1+乙+1；

且什|<EL±1<EL±1<...<LLI<1AL

"2-22--T~2,,+|

而b是一个有限数，.「"eN,使*.]=0

(a,b)=(d/)=(f,G=(乙也)=…=(%*)=(，"，0)=。,存在其求法为：

(a,b)=(b,a-bs')=(a-bs,b-(a—bs)sj=•••

.-.(76501,9719)

=(9719,76501-9719x7)

=(8468,9719-8468)

=(1251,8468-1251x6)

MV•••

=(3,1)

=1

4.证明本节(1)式中的〃<3改

log2

证：由P3§i习题4知在m式中有

0=*<小保《梦4Y台弓，而总

」.I除，24,...〃<嚏"=置’即三置

§3整除的进一步性质及最小公倍数

1.证明两整数a,b互质的充分与必要条件是：存在两个整数s,t满足条件ox+初=1.

证明必要性。假设(。,加=1,那么由推论知存在两个整数s,t满足：as+bt=(a,b),

as+bt=\

充分性。假设存在整数s,t使as+bt=l,那么a,b不全为0。

又因为(a,b)\a,(a,b)\b,所以(。,力|心+」)即(〃又)|1。

又(〃,))>0,(a,b)=1

2.证明定理3

定理3…,|a“|]

证：设[a”％，…，4』=班，那么《I小。=1,2,…

：.\^||«2](1=1,2,•••,«)又设口4I,…,1%|]=加2

那么祖J"%。反之假设|q||"%，那么《|啊，

从而m,=m2,即…,a,J=[|qI/4I，…，1。”口2

3.设a.x"+।+••■+qx+a。(1)

是一个整数系数多项式且为，。“都不是零，那么(1)的根只能是以劭的因数作分子以a,,

为分母的既约分数，并由此推出后不是有理数.

证：设(1)的任一有理根为“，(p,q)=l,g>l。那么

q

a

„-\----\-at—+a0-Q

qqq

n

a„p"+an_Kp~'q+---+afpq"~'+aoq"=0⑵

n

由(2)-anp"=+■■■+atpq~'+a(}q",

所以q整除上式的右端，所以q|%p",又(p,q)=l,q>l,

n

所以(％p)=l,：.q\an；

nnn

又由⑵Wanp+an_lp~'q-i—+aipq"~'=-aoq

因为p整除上式的右端,所以因|44",(p,q)=l,q>l,所以⑷,p)=L'-p\a„

故(1)的有理根为且p|4,q|%。

q

假设0为有理数，x=y/2,:.X2-2=0,次方程为整系数方程，那么由上述结论，可知

其有有理根只能是

±1,±2,这与/为其有理根矛盾。故0为无理数。

另证，设正为有理数(p,q)=l,g>l,那么

q

2=4,二2夕2=p2,.・.(p2,g2)=(2q2,p2)=q2>i

q-

但由(p，9)=l，4>l知(p2,/)=l,矛盾，故6不是有理数。

§4质数•算术根本定理

1.试造不超过100的质数表

解：用Eratosthenes筛选法

(1)算出Ji55=10a

(2)10内的质数为：2,3,5,7

(3)划掉2,3,5,7的倍数，剩下的是1()()内的素数

将不超过100的正整数排列如下:

-423-45-67-8-9-W)

11+213444517+81929

24-2323242526272930

31%招3435稣37招3940

41424344454647484950

54§25354穷575960

6162然6465666768的70

7173737475%衿处7980

^4-S28384躇8687S88990

9193939495%979«99+W

解:因为8|848,所以81AA=82798848=8x10349856=23x8,

又8|856,所以8|B,B=8x1293732=23XC,

又4|32,所以4|C,C=4x323433=22XD

又9|13+2+3+4+3+3),所以9|D,£)=9x35937=32xE,

又9|13+5+9+3+7),所以9|E,E=9x3993

又3993=3x1331=3x1-

所以4=28351r；

同理有81057226635000=23-33-54-73-112-17-23-37«

3.证明推论3.3并推广到n个正整数的情形.

推论3.3设a,b是任意两个正整数，且

a=p"'-P22...p：,a,>0,i=,

b=p"P守..P3々NO,i=l,2,…，左,

那么(a,h)=p：1•...,[a,b]=.pp...成,

其中%=minQ,笈)，6=min(%,月),i=l,2,…,k

证：=min(a,.,力)，二0</,.<a,.,0<<隹

PJIPta',P-1IPi,(i=1,2…女)

flP?flP：,flP?flP.A.

i=li=li=\/=1

:.P\P22•••P/*I(a,b)，又显然(a,b)\pfp,…p『

1

P2•••p?=(a,b),同理可得p：成…p?=[a,h],St=max{%,以}

推广

设q=pf"P22'­-PF，4=PRpp?",%=PFPa…p?*

(其中Pj为质数j=1,2,…,k,4为任意n个正整数i=1,2,,4/0),那么

PFPF…p『=(4,4,4,),Ya=酗鸟}，j=i2…,k

P\'P22•,,Pkk=[^,a,---,a],4=max{4/，j=1,2,…,k

2nJ\<i<nJ

4.应用推论3.3证明§3的定理4(ii)

证：设a=p；底…p泻b=…p，,

其中pi,。，…,p*是互不相同的素数，即A(1</<^都是非负整数，有

(a,b)-p,P2•­•p34=min{4，4},\<i<k,

k

[a,b]-Py'P2'••Pk'"=max{4，4},l<i<ko

由此知(a")&b]=Y\p产=npk。⑷+M{即即=「Jpai+fii=ab；从而有[a,b]=—

;=7/=?z=F(。力)

5.假设20+l是质数(n>l),那么n是2的方暴.

证：(反证法)设〃=2"(/为奇数)，

那么2"+1=2*+1=(22*)/+1=(2?+1)[2%口)一22<<,-2)+-■■+1]

1<2"+l<(22*y+l=2"+l,

...2"+1为合数矛盾，故n一定为2的方塞.

§5函数［x］,{x}及其在数论中的一个应用

1.求30!的标准分解式.

解：30内的素数为2,3,5,7,11,13,17,19,23,29

■301「30］「30］「30］「30一

%=T+M++F+F+…

=15+4+3+1+0=23

%=样卜偿卜愕卜愕卜…=1°+3+1+。=14

%=图+愕H当卜…=6+1+。=7

30303030

«7=y++…=4+0=4,a\\++・••=2+0=2

不11F

30303030

++…=2+0=2,a\3++…=2+0=2

13132

a17+•••=1+0=1,a,9=«19=a23=029=1

3O!=223-314-55-74-1121321719-23-29

2.设n是任一正整数，a是实数，证明：

n-1

a+------=\na\

n

证：⑴设[a]=m.那么由性质II知v〃2+l,

所以nm<na<nm+n,

所以，所以mK'""I<+1,又在m与m+1之间只有唯一整数m,

n

所以[口]=加=团.

n

kk+1

(ii)[证法一]设一V{a}<-----，左=0,1,2,…，〃一1,

nn

那么k<n{a}<k+\.[na]=n[a]+k

LX/•，,..iZ+l+i-i、ri

①当i+l1时n,{fa}+—v-------<1,[«+—]=[a];

nnn

②当i+k>n时,2>{a}+—>>1,[«+—]=[<7]+l;

nnn

rrrI3r〃-I,

[.[a]+[aH—]+•••+[aH------]

nn'

〃一Iin-\-k:〃-J'

=£[a+T=X[«+-]+X[a+T

?=0ni-0〃i=n-k〃

=(n-k)[a]4-k([a]+1)

=ii[a]+k

M-li

Z[a+T=[〃a]

/=<)n

I证法二]

«-1J

令/(a)=+T一团团，

2。几

1H-l；I1

・・・f(a+—)=Z[a+---J-[n«+l]=/(a)

〃,=o〃

I"-1；_(_i

・・•f(a+—)=£[a+——]一+1]三f(a)

〃,=ort

丁./(a)是以工为周期的函数。

n

又当ae[0,1)时,/(a)=0—0=0,aeR,/(a)=0,

?一|,1

即+—]=[〃0]。

,=0〃

[评注]:[证一]充分表达了常规方法的特点，而[证二]那么表现了较高的技巧。

3.设。，夕是任意二实数，证明：

(i)口]-[0=口-0或[a-0+1

(ii)[2a]+[2j3]>[a]+[a+j3]+[j3]

证明：⑴由高斯函数[x]的定义有

tz=[«l+r,/?=[/?]+5,,0<r<l;0<5,<lo那么

a-/3=[a\-[/3]-\-r—s,r—s<1

当r-sNO时,[a—/7]=[0]—[夕]

当r-s<0时,[a-夕]=陵]-[仞-1

故[a-/]=陵]-[仞或陵-句+1=囱-[尸]

(ii)设a=[a]+x,月=[/?]+y,O<x,y<1,

那么有04x+y={a}+{，}<2

下面分两个区间讨论：

①假设()<x+y<l,那么[x+y]=O,所以[a+£]=囱+[£],所以

[2a]+[2fi]=[2[a]+2x]+[2[j3]+2y]=2[a]+2[/3]+2([x]+[y])>2[a]+2[p]

[«]+[0+[0+[a]=陵]+[a+口+[0

②假设lWx+y<2,那么[x+y]=l,所以[a+尸]=[a]+[仞+1。

所以

[2a]+[2/7]=[2[a]+2x]+⑵0+2y]

=2囱+2网+2(㈤+[y])

>2[a]+2[p]+2([x]+[l-x])

(之]一.V〉

=[a]+[j3]+[/3]+[a]+2+2([x]+[-%])

>2[a]+2[^]+l

=[a]+[a+j3]+[J3]

(ii)(证法2)由于a,2对称，不妨设{a}2{77}

[2a]+[2/3]=[2([a]+{«})]+[2([^]+{/?!)]

=2[a]+2[仞+[2{a}]+[2{0]

>2[a]+2[^]+[{a}+{^}]

=[a]+[/?]+([a]+[£]+[{0}+{£}])

=[用+[£]+[[0]+{0}+[尸]+{0]

=囱+口+0+网

4.(i)设函数八>)在闭区间QWxKR上是连续的，并且非负，证明:和式

w丁(必

Q<x<R

表示平面区域QKxWA,0<y</(x)内的整点(整数坐标的点〕的个数.

(ii)设p,4是两个互质的单正整数，证明：

q-1

2日2甲号2

(iii)设r>0,7是区域避+),2=「2内的整点数，证明:

W周2

T=1+4[r]+8

0yl

(iv)设n>0,T是区域4>0,y>0,xy<n内的整点数，证明:

T=22一图-［何

0<x<vn

证明：（略）

5.设n是任一正整数，且n=a0+aip+a2P2+…，p是质数，OMa^Vp,证明：在n!的

标准分解式中，质因数0的指数是

,n-S

h=------n,

P-1

其中Sn=a0+%++….

证明：在n!的标准分解式中，质因数p的指数有限，即

2£

n=a0+a1p+a2pH---1-afp/0<a,<p

所以

nnn

h=+~^2+,,,+

P-LPpf

f2

=(aj+a2p4---F+(a2+Q3P---Fatp")H---1-at

2

=Q1+a2(p+1)+Q3(p+p+1)d---F%(pLl+pt-2---1_1)

而

n—S1

----=------71ai(P-1)+a(p2-l)+a(p3-l)+-+a(pf-l)]

p—1p—123t

2t_2

=%+a2(p+1)+a3(p+p+1)4---1-+pH---F1)

L

P-1

第二章不定方程

§2.1习题

1、解以下不定方程a)15x+25)，=100Z?)306x—36Oy=630

解：a)原方程等价于：3x+5y=20显然它有一个整数解xo=]O,yo=-2,

,x=10-5/

故一般解为《。=0,±1,±2,…)

y=—2+3t

与原方程等价于：17x-20y=35显然它有一个整数解为=—7x35,%=—6x35

“fx=-7x35+20»

故一般解为《(t=0,±1,±2,---)

[y=-6x35+17/

2、把100分成两份，使一份可被7整除，一份可被11整除。

解:依题意即求7x+lly=100的正整数解，解得%=8,%=4

…口fx=8-llr

一般解是：《(t—0,±1,---)

y=4+7/

但除f=0外无其他正整数解，故有且只有10()=56+44

3、证明：二元一次不定方程ax+by=N,a>0,b>0,(a,b)=l

NTN,

的非负整数解为或—+1

abab

证明：当N<0时，原方程没有整数解，而—+1<0故命题正确

_ab_

当N=0时，原方程有且只有一个非负整数解(0,0)而匹=0—+1=1

/\_ab\[_^b

因为(a,h)=l所以

原方程有整数解(%%),%=(-1)-1{如…必_JN,1=(-1)"{%,••、％}N

其中q=[a,%,%，…，纵]，由于。>匕>0,故飞,先中一正一负,可设x>0,y<0

b~

原方程的一般解是：=一初。=0,±1,…)

要求％—420，%+血之0=包2,2—比，

ba

仅当是整数时，才能取-瓦]，否那么-&

aaa

故这个不等式的整数解个数T是：

当是整数时T=①

haba

因而—=^2-+A=T=上+1

abbaab

当22比=E+%+1

aaba

N

因而所以(p(m)

ab

x=x-bt

证明2：二元一次不定方程ax+by=N的一切整数解为n“，rwZ,于

y=y0+at

是由xNO,yNO得一迎金42，但区间［_丛,丛］的长度是1，故此区间内的

ahabab

整数个数为［里］或［△］+1。

abab

4、证明：二元一次不定方程cvc+by=N,(a,b)=l,a>\,b>\,当N>ab-a-b

时有非负整数解，N=ah=a=b那么不然。

证明：先证后一点，当N=ab—a—b时,原方程有非负整数解(/,%)

那么d=(m,,m2).

4-1,a|y04-1x0+1=bk,y0+1=ah9k>\.h>1

=>ab^k+/?)=ah,k-\-h>2,这是不可能的。

次证，当N>ab-a-b时，因(a,b)=1,故原方程有整数解(x0,y°),一般解是=0,±1,…)

要求xo-bt>O,y()-GN0=>-比会证明存在满足这个不等式的整数，=力可取使

ab

x0=htQ+r(0<r<Z?)于是对于这个％有：

x-bt()=r</7-1=>r0>———而

y()+at。NH—(%—〃+1)—(by。+ctx^—uh+a)——(N—cih+a)>一(ab—ci-b—cih+ci)——1

bbbb

y°+at。20t°之—―

a

这就证明了当N>"-力时，原方程有非负整数解.

1.证明定理2推论。

推论单位圆周上座标都是有理数的点(称为有理点)，可以写成

(±E'±E)或(±滔寿'土亦)

的形式，其中。与〃是不全为零的整数。

/H

证明：设有理数尤=L,y="WO)满足方程3+y2=1,即『+/二加2,

mm

222222

于是得I=±2abd,n=±(a-b)d,tn=±(a+b)dI=±(a-b)dfm=±2abd,

,9.।./.2aba?-b~\_p.za~-b~2ab\l-

m=±(cr+b2)df,由止(l匕ZF得q(zx,y)-(±^-----r,------------------------------------7)。反之，

a+ba+ba+Z?a+〃

代入方程-+y2=i即知这样的点在单位圆周上。

2.求出不定方程了2+3y2=z2,(x,y)=l,x>O,y>O,z>O的一切正整数解的公式。

解：设不定方程f+3V=z2,(苍y)=l有解那么

22

(1)3/z-x或3/z+x因为3y?=z-x=(z-x)(z+x)

=>3/(z—x)(z+x)=3/z-元或3/z+x

X+3y=Zny=-^--(z—x)或者y=(z+x).丁

得3/z+x或31z-x

以下不妨设3/z+x

27

②(x,z)=l,设(x,z)=d4ijd/x,d/znd/3y=Z~9~

若,3/d,=9/1£=9/3y~=3/y=3/(x,y)与(x,y)=1矛盾!

这样(3,d)=I=>d/ynd/y(・.・Q"73y)而4/工=>"/(羽丁)nd=1

@(z4-x,z-x)=lgJc2，设/=(z+x,z-x)=〃(z+x)-(z-x)=2x,

〃(z+x)+(z-x)=2zn/7(2x2z)=2即t=1或，=2

z+x

④假设(z+及Z-x)=1,则------,z-x=1,

3

从而3y~=(z+x)(z-x)=>J=z；x.(z—x)

由引理可设亨=",z—x=j,y="

从而三，为证得x,z为整数，(x,z)=l,

必须有a,b均为奇数，且3々2＞人2

⑤假设(z+x,zr)=2n言，宁=ln平,3卜

2\2z+xz-x

从而3y=(z+x)(z-x)=>

62

设=<2'~^=1>弋=阪即x=Bq?一万,y=2ab,z=3a'+fy~,

o22

其中a,b为一奇一偶,且有(〃,))=1

22

4.解不定方程：x+3y2=z,x>09y>0,z>0,(x,y)=1o

解：设(z-x,z+x)=d,易知d==1或2。由(z-x)(z+x)=3y2得z-x=3da2,

z+x=db2,y=dab或z-x=db~,z+x=3da2,y=dab,a>0,Z?>0,(a,b)

=Io(i)当d=l：x=——"』y—z="十九,a>0,b>0,(〃，〃)=

22

2222

1,31b,a,b同为奇数；(ii)当d=2：x=\b-3a\,y=2abfz=Z?+3af

a>0,b>0f(a,b)=1,3//?,a,b一奇一偶。反之，易验证(i)或(ii)是原

不定方程的解，且x>0,y>0,z>0,(x,y)=1o

2A

3.证明不等式方程K+y=z,(x,y)=l,x>O,y>O,z/x的一切正整数解.

可以写成公式:%=4的/―//),y=Ia+b4-6ab21,z=a+b2

其中a>0,/?>0,(。,5)=1,。,丘单一双

证明:由定理1知道原方程的解是x=2cd,y=c2—d2,z=c2+d；

c>d>0,(c,<7)=l.且c,d为一奇一偶，

其中，c=2ab,d=，一b：a>b>O,(a,b)=1,且a,b为一奇一偶.

所以X=4"(Q2—//),y=|+|,2=。2+52是原方程的正整数解

(x>0,y>0,z>0,(x,y)=1,2/x,且片+//是奇数,

原方程正整数的解有：

(0,0,0),仅,,卜〃；0,±4(±4的/-//),±(〃4+//-6〃方),土(〃2+加),

(±(。4+//-6〃方),±4的-加,±(〃2+//)),

6.求方程/+y2=的满足(x,y)=],2|x的正整数解。

解：设x,y,z是/+y2=z4的满足(尤，y)=1,2|x的正整数解，那么x=2ab,

y=a2-b2,z2=a2+h2,a>b>0,(〃，b)=l,a,b一奇一偶,再由z2=&2+

得〃二2wv,b=u2-v2,z=w2+v2或a=u2-v2,b=2wv,z=u2+v2,

w>v>0,(w,v)=1,u,u一奇一偶，于是得x=4uv(u2-v2),y=|/+/_6M2V2|,

z=u2+v2,u>v>0,(w,v)=1,“，丫一奇一偶。反之，易验证它是原不定方

程的整数解，且工>0,y>0,z>0,(x,y)=1,2|xo

其中正负号可任意选取.

第三章同余

同余的概念及其根本性质

1、证明⑴假设A%..该三B*G(modm)

x.=yz(modm)>i=L2,、、、，k

那么ZAa,..q¥，…琛三ZBa.”年…*(modm)

a，…囚,.皿

特别地，假设a：三2(modm),i=0,1,…,〃那么

nnnx

anx+a〃_]X"7+・・・%三bnx+bn_xx~+・・•+%(modm)

(ii)假设a=b(modm),k>0,❷。％=/?A:(modmk\

(iii)假设a三b(modm),d是a,b及m的任一正公因数，那么色三2(mod'),

bdd

(iv)假设a=b(modm),djm、d>0.那么a=b(modd).

证明：⑴据性质戊，由七三y(modm),i=1,2,・・・,2.

得x：三y：,(modM,i=12・・・,Z,

进一步，那么

…婚三九:…琛(mod㈤

最后据性质丁，可得：

ZA/”,邛…琛三ZB%,.、以短…碟(modm)

(ii)据定理1,a=b(modm)^m/a-b^

,/k>0,.,.mk/k(a-b)=ka-kb

又据定理1,即得妨三始(modmk).

(iii)据定理1,a=b(modm)=>m/a-/?,KPa-b=ms(sez)

j,jja-bmRRc1bm

dIa、b、zzz,d>0,..------——s,即.....——,s,

ddddd

仍据定理1,立得4三2(mod')，

bdd

(iv)据定理1,a=b(modm)a-a=ms.(sez),

又,：=dt,tGZ,

^a-h=ms-d(st),stGZ,

/.a=b(modcl).

2、设正整数a=勺10〃+a〃_J0〃T+・・・/,0K4v10

ni

试证11整除的充分且必要条件是11整除Z(-l)4-

i=l

证明：:IO三一l(modl1),.•.由上题⑴的特殊情形立得

a=+Q〃-J0"'+…/=。〃(一D"+•^«0(modl1)

a三Z(-D'q(modl1),

i=O

=a,

/i=0

3.找出整数能被37,101整除有判别条件来。

解：­.-1000=l(mod37)

故正整数a=41000*+矶100(产+…％,04a,.<1000

立缰371ao37

//=0

•.-100=-l(modl01).

故设正整数a=久1()()'+瓦_1100~+…瓦,0<b,<100',

立得101/ao101/'(-1)'/?,..

/i=0

4、证明6明I232+1

证明：三256(mod641)

二216=2562=65536=154(mod641)

232=1542=23716=-l(mod641)

即641|232+1

5、假设4是任一单数，那么三i(mod2"+2),(n>l)

证明：(数学归纳法)设。=2m+1

(1)〃=1时，a2=(2m+l)-=4/«(/w+l)+lsl(mod8),

结论成立。

(2)设〃=A时，结论成立，即：

(2/n+l)2；-lsO(mod2A+2)=>(2//z+l)2*-1=2A+2Z,(fwz)

而一1=(/-1)+1)=(42*-1)(/-1-2)

^(2k+2t^+2-2k+2-t

=t2-22M+t-2k+3

=t-2M(t-2k+i+\)

=0(mod2A+3)

故〃=左+1时，结论也成立；时，结论也成立。

证明：假设2[a,〃是正整数，那么/'三1(mod2"+2)。⑷

设a=24+1,当”=1时，有

a2=(2k+Ip=4k(k+1)+1=1(mod23),

即式(4)成立。

设式(4)对于"=左成立，那么有

cr=1(mod2*'+2)=>a2*=1+q2k+2,

其中qeZ,所以

=+琥八2)2=i+/2*+3=1(mod2k+3),

其中“是某个整数。这说明式(4)当〃=%+1也成立。

由归纳法知式(4)对所有正整数〃成立。

(z)1535625；(n)l158066

解：(Z)1535625=33X54X7X13；

(zz)l158066=2X3272X13x101

§2剩余类及完全剩余系

1、证明》=“+〃'-、，u=0,1,2,■■■,p'-1,rWs是模p'的一个完全剩余类。

证明：显然对的不同取值，x共有p'£p'=p'个值，故只需证这样的p，个值，关于模炉

的两两互不同余。

假设4+p'~'vl=u2+(modp*)

=%_u2=p'T(v)-v2)(modp')

npi|ux-u2,即场三七(mod//-')=>%=与

sss

=>p~'v{=p~'v2(modpj=>V]sv2(mod//)=>、=v2

%=%或巧W%时，

xs

M,+p~'vtJ^U2+p~'v2(modp").结论成立。

2、假设犯，加2,是攵个两两互质的正整数，斗,工2,…,X*分别通过模班的完全

剩余类，那么

AfjXI+M2^2+•••+M/卜

通过模仍加2…幽=加的完全剩余系,其中m=肛风，』=1，2,…次

证明：(数学归纳法)

(1)根据本节定理3,知％=2时，结论成立。

(2)设对整数攵-1,结论成立，即假设"小叫,…,mj两两互质，令

="；X[+%左2+…+MTX-I，当玉，心…，王—1分别通过模町，加2,…，叫-1的完全剩

余系时，s’必过模

m=的完全剩余系，其中叫M；=m(，=1,2…左一1)。

现增加叫，使(g,外)=1(，=1,...攵一1),

令Mi=Mkmk（1，…左-1）,m=Mk=mAm2...tnk_{,m=mkMk=tn}m2...mk

那么易知。勺，加2，…，？）=（町i，%,）=1，

再令x=+/4s',

当迎过模忆的完全剩余系，s过模的完全剩余系时，据本节定理3,x必过模

m=mkMk=m^n2...mk的完全剩余系，即对k结论成立。

3、（i）证明整数-”，…-1,-0,1,…,"（"=上二］）中每一个整数有而且只有一种方法表示成

3-1

3"居+3"工_]+...3x+x0.......O

的形状，其中看=一1,0,l（i=0,l,..."）；反之，❶中每一数都之一“且W”,。

（ii）说明应用〃+1个特别的祛码，在天平上可以量出1到H中的任意一个斤数。

证明：（i）当氏=一1,0,1«=0,1,...〃）时，❶过模24+1=3向的绝对最小完全剩余系，也就是

❶表示［一中的2〃+1个整数，事实上，当王时，共有32个值，且两两互不相

等，否那么

3"x"+3"'x“_|+…3X］+XQ=3"x"+3"'x“_|+…3X］+

=>3"(%“7")+3"-'(工"_]一/_|)+...3(5-x,)=-x0

=>31x0-x0=>x0=x0.

此即

3”T(左一七)+3"2(x,i—)+...(x-x)=0

=>3|Xj-xx=>x)=%=>...=>xn=xn

又❶的最大值是3"+3"T+...3+l=^——二H

3-1

最小值是—3"—3"T—3—1=—H

所以，结论成立。

（ii）特制〃+1个祛码分别重1,3,32,...,3"斤，把要称的物体，＞（4）

及取-1

/=!

的祛码放在天平的右盘，巧取1的祛码放在左盘，那么从［i］的结论知，当当取适当的值时,

可使7=3"5+3"-1*,1+...3*+/.之值等于你所要称的物体的斤数(4")。

4、假设叫，牡，…，恤是K个两两互质的正整数，x[,x2,...xk分别过模叫，加2，...,?的完全剩余

系，那么

X+仍工2%，加2工3+…+町，”2,…，恤/........❷

通过模町，机2,…,，%的完全剩余系。

证明：(数学归纳法)

(1)K=2时，元],々分别过模"4，%的完全剩余系时，

玉+I4%共有町根2个值，且假设

玉+n\x2三X+gxKmod叫叫)=>仍(尤2-^)=(modm,^)

=>加[4一玉，且w_后=———(mod?7^)

““风

r

=>M=X',x2=x2,即左=2时结论成立；

⑵设当尤2,…,L分别过模“2,…,/的完全剩余系时，

X2+加2工3+…+叫板…%_]先过模加2…砥的完全剩余系。

因为(犯，?…％)=1，由本节定理2得，

班(x2+m2七+…+网…外-山)亦过模m2…砥的完全剩余系。

当西,々，…,皿_],xk分别过模/叫,m2,・・•，?一,mk的完全剩余系时，

2有班叫…外个值，且据归纳假设，

假设西+叫工2+…+町…"”-2々-1+小…叫_吊

,,

三工：+H-----b•••mk_2xk_]+/??!•••mk_]xk(mod町--mk)

=>Xj=x：(mod"%)；x2+ntyXyH-----bn72•••mk_]xk

=x\H----\-m2•••〃i”[X(mod〃22…mJ

r

n%=X(mod/721),x2=x^modrn^),...»xk-xk(modmk)

=>=X；,x2=%2

mx

所以玉+mxx2+