《初等数论(闵嗣鹤、严士健)》第三版

《《初等数论(闵嗣鹤、严士健)》第三版》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

cl第一章整数的可除性§!整除的概念•带余除法1.证明定理3定理3若q,a2,--,a“都是相得倍数,卯も，…，依是任意〃个整数,则+q2a2+…+q“a”是相得倍数.证明:；a”％…,％都是〃，的倍数。,存在〃个整数0いタ2,…p“使at=ptm,a2=p2m,…，an=pnm又一,%,…,q”是任意〃个整数q四+%ム+…+4.。”=qlp{m+q2p2m+---+qnpnm=(Piqi+q2P2+~+q“p“)m即qtat+%ム+…+%4是〃1的整数2.证明3|〃(〃+1)(2〃+1)证明vn(n+1)(2〃+1)=n(n+l)(/i+2+n-1)=〃(〃+1)(m+2)+(〃ー1)〃(〃+1)又•.•〃(〃+1)(〃+2)，(〃ー1)〃(〃+2)是连续的三个整数故31〃(〃+1)(〃+2),3|(n-l)M(/i+l)/.31〃(〃+1)(〃+2)+(〃ー1)〃(〃+1)从而可知31〃(〃+1)(2〃+1)3.若0¥()+外〇是形如ax+by(x,y是任意整数,a,b是两不全为零的整数)的数中最小整数,PliJ(ax0+)I(ax+by).

1证:,•・。カ不全为〇・・・在整数集合S={ax+by\x,yeZ}中存在正整数,因而有形如ax^by的最小整数叫+如Vx,ygZ,由带余除法有axby=(ax0+byG)q+r,04r0则令s==a-bs=a-^—^-b,则有^lb=a-^咏。.•昨WBl--

2.得证.下证唯一性当b为奇数时,设a=bs+f=加]+ム则レーム|=|b(S]-s)|>网而か省Ml碧，”心M+同训矛盾故s=s"=ム当b为偶数时,s」不唯一,举例如下:此时ン为整数へb-b,へ,b、hiib3.-=&.l+-=&.2+(--),/]=25W-2§2最大公因数与辗转相除法1.证明推论4.1推论4.1a,b的公因数与(a,b)的因数相同.证:设d’是a,b的任一公因数,，d'|a,dr|b由带余除法a=bq{+厶,/?=4%+り‘・・・，72=「国用，°=rn+lr„

3わ的公因数与5,。)的因数相同。2.证明:见本书P2,P3第3题证明。3.应用§1习题4证明任意两整数的最大公因数存在,并说明其求法,试用你的所说的求法及辗转相除法实际算出(76501,9719).解:有§1习题4知:bwZ,bw0,ヨsJ£Z,使〃=加+rJf区一。,ヨS1,ム,使/?=+ム,|ム区!•«ア,…,如此类推知:ヨS〃，ム，0ー2=レード〃+ム;ヨs”+i，ム+1，ムー1=ムL+】+ム+1；且I.i

4证:由P3§1习题4知在(1)式中有°=か<い号4,〈…く券《，而へ.・”2,，2“。,.•・〃勺。g/=皿,即〃4皿T2log2log2§3整除的进ー步性质及最小公倍数1.证明两整数a,b互质的充分与必要条件是:存在两个整数s,t满足条件如+初=1.证明必要性。若(a,b)=l,则由推论1.1知存在两个整数s,t满足:〃s+初=(〃,/?),as+bt=1充分性。若存在整数s,t使as-i-bt=l»则a,b不全为〇〇又因为(a9b)\a9(a9b)\b,所以又因|as+加)即伍,6)|1。又(スの>0,/.(a9h)=12.证明定理3定理3[al,a2---,a„]=[|at|,|a21•••,1a„|]证:设[。い。2,…,。」=叫，则ルム(i=l,2,…・・.|もII叫(i=l,2,…又设口ー・/I，…,a\]=m2则m2\m]O反之若|m2,则at\m2，.,・机]|m2从而㈣=加2,即…，叫=ロ％I，…，1。/23.设しバ+。〃_]ス〃ー+…+。拝+。0(1)是ー个整数系数多项式且へ,。〃都不是零,则(1)的根只能是以。。的因数作分子以ム为分母的既约分数,并由此推出血不是有理数.证:设(1)的任一有理根为ム,(p,q)=l,q>l。则q（"）"+an-\（K）〃T+…+q"+%=0qqq

5a“P〃+a,iP”“q+…+〃]Pグ"+旬グ=〇（2）由（2）-anpn=jp"-%+…+%pグ"+aQqn，所以q整除上式的右端,所以り丨ムP",又（p,り）=1,り>1,所以（り,p"）=L「•qk；又由（2）有〃"p"+*_]p"%+…+qpグ々二ー〃〇グ因为p整除上式的右端,所以尸为〇グ，（p,q）=l,り>1,所以（グ,p）=l,.*.pIan故⑴的有理根为ム,且q假设及为有理数,x=V2,.".x=ヒ,.ゝ2q2=p2,.\（卩2,ザ）=（2q2,p2）=q2>1Q但由（p,q）=l,タ〉1知（//,ダ）=1,矛盾，故也不是有理数。§4质数•算术基本定理1.试造不超过100的质数表解:用Eratosthenes筛选法（1）算出。100=10a(2)10内的质数为:2,3,5,7-2=0I次方程为整系数方程,则由上述结论,可知其有有理根只能是±1,±2,这与为其有理根矛盾。故正为无理数。另证，设正为有理数8=K,（p,q）=l,g>l,则q

6(3)划掉2,3,5,7的倍数,剩下的是100内的素数将不超过100的正整数排列如下:7-8-9-W17+«1920272829503758594047484950575859606768697077787980878889909798994002.求82798848及81057226635000的标准式.解:因为8|848,所以8|んん=82798848=8x10349856=2'xB,又8|856,所以8|B,B=8x1293732=23xC,又4|32,所以4|C,C=4x323433=22xD又9|(3+2+3+4+3+3),所以9|D,D=9x35937=32xE,又9|(3+5+9+3+7),所以9|E,E=9x3993又3993=3x1331=3x1产所以A=2835113；同理有81057226635000=23-33-54-73-112-17-23-3703.证明推论3.3并推广到n个正整数的情形.推论3.3设a,b是任意两个正整数，且a=p?'-P22p„"0,i=l,2,--,k,112+54--442224252627292+4243444546474S494+525455565759544264656b=pF•P?■•…Pケ,dNO,i=l,2,…，k,

7则(a,b)=pMp/……,[a,b]=p,.p/♦p?,其中先=min(%,以)，^=min(a,,^),i=\,2,---,k证:,/=min(%,4)，.•.0l),则n是2的方嘉.证:（反证法）设〃=2'（/为奇数）,

8则2"+1=2*,+1=(2プy+1=(22*+1)[22*(/-1)-22rz-2)<1<2?+1<(22*)/+1=2"+1,二2"+1为合数矛盾,故n一定为2的方塞.§5函数[x],{x}及其在数论中的ー个应用1.求30!的标准分解式.23,29解:30内的素数为2,3,5,7,11,13,17,19,=15+4+3+1+0=23<73=30T+•••=10+3+1+0=14a73030T+■•=6+1+0=7+・••=4+0=4930I「3011J|_11230I「30+T13J|_132+,••=24-0=2,a\j3013=2+0=230301n,,%7=五+谈+…=1+0=1，«19=a19=a23=a2g=l工30!=223-3,4-55-74-112-132-17-19-23-292.设n是任一正整数，a是实数,证明:(ii)[«]+1(X+—n+•••+n-1a+n=[〃a]

9证:⑴设［a］=m.则由性质II知相く。＜〃?+1,所以nm{a}+丄N421,[a+2]=[a]+l;nnn1n-\・・.[a]+[a+上]+…+[a+-—]nnn-\1n-\-kjn-\:=Z1a+T=X[«+-]+Z[a+Ti=Q〃i-0〃i=n-k〃=(n-え)[a]+&([a]+1)=〃[a]+k/.>[a+—]=[〃a]Mn［证法二］令…乎+2孙n-l・・・y(a+-)=Y[a〃i=0a+—]-[na+l]=/(a)n.•./(a)是以丄为周期的函数。n又当ae[0,1)时,/(a)=0-0=0,aeRJ(a)三〇,即£[a+-]=[〃a]。i=on

10[评注]:[证ー-]充分体现了常规方法的特点,而[证二]则表现了较高的技巧。3.设a,万是任意二实数,证明:(i)[a]-[夕]=[a-夕]或[a-夕]+1(ii)[2a]+[2/3]>[a]+[a+/3]+[/3]证明：(i)由髙斯函数[x]的定义有a=[a}+r,p=[^]+5,0ff]+1=[a]-[fi](ii)设a=[a]+x,£=[4]+y,04x,y<1,则有04x+y={a}+{£}<2ド面分两个区间讨论：①若04x+y2[a]+2网=[a]+[用+[0+[a]=[a]+[a+夕]+[切②若14x+y<2,则[x+y]=l,所以[a+£]=[a]+[尸]+1。所以[2a]+[2J3]=[2[a]+2x]+[2网+2y]=2冋+2网+2([x]+[y])>2[a]+2[/?]+2([x]+[l-x])...Xと]つ，)=[a]+[切+[切+[a]+2+2(印+[r])>2[a]+2[/?]+l

11=[a]+[a+仞+[仞(ii)(证法2)由于a,タ对称,不妨设{a}N{夕}[2a]+[2/7]=[2([a]+{a})]+[2(げ]+{夕})]=2[a]+2网+[2{a}]+[2{夕}]N2[a]+2[夕]+[{a}+{夕}]=[a]+[#]+([a]+[£]+[{a}+{6}])=[a]+[£]+[[a]+{a}+[£]+{尸}]=[a]+[a+ガ]+/]4.(i)设函数れ噂在闭区间。4x4R上是连续的,并且非负,证明:和式gピ21表示平面区域QWxWR,00,ア是区域ズ+アス4芦内的整点数,证明:ヂ=1+4(ア]十8)レダー・]一・卜3(iv)设n>0,T是区域常>0,y>0,xy^n内的整点数,证明:

12T=2ヨー时证明:(略)4.设n是任一正整数,且n=a()+aが++…，p是质数,。。4^"り++YP+・・・+-り+…+at=血+a28+1)++p+1)+•»•+%(pL，++…+1)而-ナ=—、・[”(?-1)+旳(?2-1)+〃ヤ》ー1)+…+-1)]p—丄p一丄=旳+C^2(P+1)+4-p4-1)+・・・+4*4*…4-1)p-1第二章不定方程§2.1习题1、解下列不定方程a)15x+25y=100b)306x-360y=630

13解:a）原方程等价于:3x+5y=20显然它有一个整数解七=10,%=-2故一般解为jc=10-5/y=-2+3/(r=0,±l,±2,-)b）原方程等价于:17x-20y=35显然它有一个整数解x0=-7x35,y0=-6x35Ix=-7x35+20/故一般解为《（/=0,±1,±2,…）[y=-6x35+17/2、把100分成两份,使ー份可被7整除,ー份可被11整除。解:依题意即求7x+lly=100的正整数解,解得x0=8,y0=4一般解是:x=8—11/y=4+7/(/=〇,±1,…)但除/=0外无其他正整数解，故有且只有100=56+443、证明：二元一次不定方程ax+by=N,a>0,b>O,(a,b)=1的非负整数解为证明：当N<0时,NabNab原方程没有整数解,而Nab+1<0故命题!E确N1।—4-1=1ab当N=0时,原方程有且只有一个非负整数解（0,0）而—=0ab因为（a,b）=l所以原方程有整数解（x0,y0）,y0=（-1）"-1•',qn.x}N,Xo=（-1）"{q2,---}N其中巴=[4],%,%,…,%],由于。>b>0,故x（）,あ中一正一负,可设x>0,y40b"-原方程的一般解是:ド="一4（/=0,±1,…）[y=y0+ar要求スO->0,y04-af>0=>—>z>,ba仅当ー&是整数时,才能取，二ー比,否则t>-比aaa

14故这个不等式的整数解个数T是:当是整数时T=［チ］T+T+1Nx0y0„N,因而ー=—+—=>T=一+1ahbaabbNab所以(p(ni)当比不是整数时ア=血ーー比=2\x=xn—bt证明2：二元一次不定方程。ス+刀=N的一切整数解为4°,teZ,于し=%+G是由xNO,yNO得一比4,4工,但区间［-&,厶］的长度是总,故此区间内的abab'ab整数个数为［*］或［包］+loabab4、证明:二元一次不定方程ax+by=N,(a,b)=l,a>T,b>l,当N>ab-a-b时有非负整数解,N=ab=a=b则不然。证明:先证后一点,当N=ab-a—b时,原方程有非负整数解(ム,ル)=>/?|x04-l,tz|y0+1=>x0+1=M,y0+1=ah,k>1,/?>1=>ab(k+h)=ab,k+hN2,这是不可能的。次证,当N>ab-a-b时,因(a,b)=l,故原方程有整数解(x〇,y〇),一-般解是｛エ閣"=0,±1,…)要求xo-bt>O,yo-GNOn-&4,く也会证明存在满足这个不等式的整数，=ん可取使abxQ=btQ+r(0

15,,而by。+〃，〇N%H—(Xq—b4~1)—(by。+ciXq—ab+a)=—(N—cib+a)>—(ab—a—b—cib+a)——1“bb"bby0+at0>0=>t0>--a这就证明了当N>姉-a-ル时,原方程有非负整数解.1.证明定理2推论。推论单位圆周上座标都是有理数的点(称为有理点),可以写成(±-^T，±4^)或(士4^，±-^7)a'+b~a+b~7a~+b~a+b~7的形式,其中a与わ是不全为零的整数。证明:设有理数x=丄,y=—(mw0)满足方程/+y2=I,gpl2+n2=m2,于是得I=±2abd,n=±(a2-b2)d,m=±(a2+b2)dsE/=±(a2-b2)d,m=±2abd,,2,2、,.uzbzヽZ,2abcT-b~\_4x/1a~~b~2ab\ヒ亠m=±(a2+b2)d,由此得(x,y)=(±-5~^-,±—-~~77,±—~-7)0反之,cT+b~a+ケa~+ba+b代入方程X?+y2=1即知这样的点在单位圆周上。2.求出不定方程x2+3y2=z2,(x,y)=l,x>0,y>0,z>0的一切正整数解的公式。解:设不定方程x?+3ザ=，，(x,y)=l有解则(1)3/z-x或3/z+x因为3y2=z2-x2=(z-x)(z+x)=>3/(z-x)(z+x)=3/z-x或3/z+x2022-Z+X/\——p--far.2/\Z一XX+3y=Zny=アセー力或者y=(z+x)--イ导3/z+x§Jc3/z—x以下不妨设3/z+x

16②(x,z)=l,设(x,z)=d^Jd/x,d/znd/3y-=z2-_x；若,3/d,n9/ズー,9/エー=9/3y=>3/yn3/(x,y)与(x,y)=1矛盾!这样(3,の=lnd/ynd/y(•.・イ/3y)而1/xnd/(x,y)nd=1③(z+x,z-x)=l或2,设，=(z+x,z-x)n〃(z+x)-(z-x)=2x,，/(z+x)+(z-x)=2znr/(2x.2z)=2即.=l或r=2④若(z+x,z-x)=1,则=1,从而3y-二(z+x)(z-x)=>.(z-x)由引理可设平=q；z-x=h2,y=ab从而三,为证得x,z为整数,(x,z)=l,必须有a,b均为奇数,且3グ>ど⑤若(z+x,z-x)=2=>z+xz-x=1=>z+xz-x=1从而3y，=(z+x)(z_x)n|jj==.デ设・^―==ガ，；=",即X=3a2-1j2,y=2ab,7=3〃ユ+//,其中。,わ为ー奇ー偶,且有(a,b)=l4,解不定方程:x2+3y2=z2,x>0,y>0,z>0,(x,y)=1〇解:设(z-x,z+x)=ム易知[=l或2。由(z-x)(z+x)=3y2得z-x=3da2,Z+x=db2,y=daい或z—x=d。“，z+x=3da2fy=dab,a>0,b>0,(a,b)=1〇(i)当d=1：x=-Ly=ab,z，a>0,b>0,(〃,/?)=1,3\b,a"同为奇数;(ii)当d=2：x=|Z?2-3a2|,y=lab,z=b2+3a2,a>0,b>0,（a,b）=1,3，わ,明いー奇ー偶。反之,易验证（i）或（ii）是原不定方程的解,且x>0,y>0,z>0,（x,y）=l。3.证明不等式方程ザ+y2=z4",y）=i,x>o,y>o,z/x的一切正整数解.可以写成公式:x=4的，ーガ）,y=|グ+ガーI,Z=q2+が其中a>0,b>0,（a,b）=1,a,ルー单一双证明:由定理1知道原方程的解是・=2しZ,丁=ピーd；z=c-+d；

17c>d>0,（c,t/）=1»且c,d为一奇ー偶,其中，c=2ab,d=〇ー-ガ,a>b>0,（a,b）=1,且a,b为一奇ー偶.所以X=4姉（ビード），y=|グ+ドー6イガ|,Z=〃ユ+/Z是原方程的正整数解（x>0,y>0,z>0,（戈,y）=1,2/ズ,且ビ+ガ是奇数，原方程正整数的解有:（0,0,0）,（0,土/土a）,（土/,0,土a）（±4的ーーガ）,±（/+ガー6イガ）±/+ガ）），（土（，+ガー6。方）,±4应オ一方）,土ば+か）），6.求方程ス2+ザ=ズ的满足（x,y）=1,2IX的正整数解。解：设ス,y,z是ズ+ザ=ズ的满足・,y）=1,2］ス的正整数解,则ス=2ab,y=a2-b2fz2=a2+b2,a>b>0,（a,b）=I,a,bー奇ー,偶,再由ス2=ガ+/72得。=2〃貧,b=u2-v2,z=w2+v2或a=u2-v2,b=2wv,z=w2+v2,u>v>0,（w,v）=1,w,v一・奇一・偶,于是得x=4wv（w2一v2）,y=|w4+v4-6w2v2|,Z=U2+V2,M>V>0,（M,V）=1,〃,リー奇ー偶。反之,易验证它是原不定方程的整数解,且ズ>0,y>0,z>0，（x,y）=1,2Ixo其中正负号可任意选取.第三章同余す1同余的概念及其基本性质

181、证明⑴若Ayq三B„.(modm)X,三yj(modm)、i=l,2,、、、,k则EA....aバ…琛三Zヂ…靖(modm)a.…,为叫…项特别地,若《三々(modm),i=0,1,…,〃贝リcix'1+ci,,x>l1+,•,da=bnxn+h】x""(modm)nn—\unn-iv(ii)若a=b(modm),k>0,dk=bk(modmk),(iii)若a三b(modm),d是a,b及m的任一正公因数,则一三一(mod—),bdd(iv)若a=b(modm),d/in,d>0.贝リa=b(modd).证明:(i)据性质戊,由七三y(modm),i=1,2,•••,レ得ず‘三y：'(modm),i=l,2,…,た,进ー步,则Aq.”ず…燈三B%...%ヂ…ガ(modm)最后据性质丁,可得:し厶いバ…パ三ZB。…ヂ…/(modm)巴…,4%…人(ii)据定理1,a三b(modm)=>加/。一い,,/k>0,/.mk/k(d—b)—kd—kb又据定理1,即得kd=kb(modmk).(iii)据定理1,a=b(modm)nzn/a一定即a-b=ms(swz),,,..d-bmBnabmdIa,b,m,d>0,•・=—s,即=—,s,ddddd仍据定理1,立得巴三ユ(mod丝)，bdd(iv)据定理1,a=b(modm)=>d-d=ms.(sgz),又二d/zn,m=dt,twz,故a-b=ms=d(st),stgz9a=伙mod").

192、设正整数。=a/0"+a“_J(rT+…<10试证!1整除的充分且必要条件是!1整除之(-1)5/=1证明:♦••10三一l(modll),.•・由上题⑴的特殊情形立得a=an\Q"+41Tl0"-'+--a0san(-l)"+an_.(ーD">+…％(mod11)a三Z(-l)’《(mod11),i=0.•.ll/aoll/£(-l)生3.找出整数能被37,101整除有判别条件来。解:vl000=l(mod37)故正整数a=aJ000"+aJt_l1000A-1+---a0,037]>,%./1=0V100=-l(modl01).故设正整数a=bs\00s+ん一1100'T+…ル,〇4ク<1〇〇，，立得101/a0101/£(-1アク.4、证明641I2奨+1证明:丁2!*m256(mod641)

20216三2562=65536三154(mod641)2コ2三1542=23716三一l(mod641)即641|232+15、若。是任一单数,则パ三l(mod2"2),(n>1)证明:(数学归纳法)设。=2m+1(1)〃=1时,a2=(2/n+1)2=4m(m+1)+1=l(mod8),结论成立。(2)设〃=セ时，结论成立,即:(2/n+1)2一1三0(mod2"，2)=>(26+ザ-1=2k+2t,(/ez)而—=ゼ_リト2*+リ=(ガーリビ-1-2)=(2"+2ガ+2フ・2イ.2イ2女+4.•勺ル+3=z-2*+3(/-2t+,+l)=0(mod2*+3)故"=た+1时，结论也成立:ユ〃ン1时，结论也成立。证明：若2/a,〃是正整数,则ダ三1(mod2"+2)。(4)设a=2た+1,当〃=1时，有a2=(2k+I)2=4k(k+1)+1s1(mod23),即式(4)成立。设式(4)对于〃=た成立,则有a2=1(mod2*+う^>a2=1+c/2k42,其中qeZ,所以aみ=(]+ナ2)2=1+q'2k+3=1(mod2t+3),其中グ是某个整数。这说明式(4)当〃=ん+1也成立。由归纳法知式(4)对所有正整数〃成立。

21(z)1535625；(n)l158066解:(z)1535625=33x54x7x13；(zz)1158066=2x3272x13x101§2剩余类及完全剩余系1、证明X=〃+0,1,2,…,p'-1,是模,,的・个完全剩余类。证明:显然对〃ノ的不同取值,ズ共有pi・p’二P、个值,故只需证这样的ジ个值,关于模p.的两两互不同余。若〃I+p''匕三〃2+P，vi(modp')=U|ー〃2—P’T(vj-v2)(modp5\=>ps~'Iu}-u2,BPWj=u2(modps~l)=>=u2=pi4=prv2(modpsj=>Vj=v2(modpり=%=v2%=〃・,或匕エv2时，%+pi匕エ〃2+Pty2(modo').结论成立。2、若叫,加2,…,町t是々个两两互质的正整数，ス1,ス2,…，七分别通过模叫，加2,…，〃”的完全剩余类,则M}x14-Af2x2H卜MkXk通过模町m2…?=m的完全剩余系,其中m=,i=1,2,…,k证明:(数学归纳法)(1)根据本节定理3,知え=2时,结论成立。(2)设对整数k-\,结论成立,即若叫,加2,…，叫ー1两两互质,令s=M、］+/ゝ2+…+aJi，当るそ,…,王ー1分别通过模㈣,叫‘…’St-1的完全剩余系时,s’必过模

22m=mxm2...mk_x的完全剩余系,其中.-m（i=1,2../-1）〇现增加”,使（叫,叫）=1（i=1,…え一1）,令A/,=Mkmk（^...k-V）,m=Mk=m[m2..jnk_x,m=mkMk=mxm2...mk则易知（叫,加2，…，恤）=（mバMJ=1,再令ス=A/セム+加び,当ム过模恤的完全剩余系,s过模的完全剩余系时,据本节定理3,よ必过模m=mkMk=叫加2・・・加人的完全剩余系，即对ん结论成立。3〃+1_j3、（i）证明整数-”,…-1,ー。」,…,//（”二）中每ー个整数有而且只有一种方法表示成3—13".し+3"1ズ〃ー]+...3x+Xq❶的形状,其中％=-1,0,1（，=0,1,…〃）;反之,❶中每ー数都2-”且《”,。（ii）说明应用〃+1个特别的祛码,在天平上可以量出1到H中的任意ー个斤数。证明:（i）当吃=-l,0,l（i=0,l,…〃）时,❶过模2”+1=3‘川的绝对最小完全剩余系,也就是❶表示[-”,”]中的2”+1个整数,事实上,当七二-1,0,1时,共有3用个值,且两两互不相等,否则3"+3"ン"_]+…3%+Xq=3"x〃+3"।x〃ー]+...3X]+x0=>3"（x〃ーx〃）+3〃セx〃_]-xパ]）+...3（X]-X]）=x。ーX。=>31x0-x0=>x0=x0.此即3"T（ムーX"）+3"-2区ニームー|）+…（ノ-X）=。=>31X]-X]=>X]=X]=>.・・=>x〃=xn3”+i_i又❶的最大值是3H+3n-|+...3+l=-——と=H3-1最小值是ー3"-3"-'-...-3-1=-77

23所以,结论成立。（ii）特制〃+1个祛码分别重1,3,32,…,3"斤,把要称的物体fシ（4）=y及取ノ的祛码放在天平的右盘，ム取1的祛码放在左盘,则从（i）的结论知，当七取适当的值时，可使ア=3エ+...3X+%.之值等于你所要称的物体的斤数（W"）。4、若叫,吗,...,“是K个两两互质的正整数,xpx2,...xt分别过模叫,加2,…,/的完全剩余系,则x,+mix2+ml,m2x3+...+mi,m2,...,mkxk❷通过模叫,啊,…,加・的完全剩余系。证明:（数学归纳法）（1）K=2时,x”X2分别过模班,“ユ的完全剩余系时，ム+团内共有m〃2个值，且若%+加1x2三x；+加］x：（mod加］加2）=>加］（x2-X；）三x；_X］（mod加］加2）f=>m］\x［-x1,x2-%2=~~—（modm2）=>Xj=x［»ム=対,即え=2时结论成立;（2）设当ス2,…,ム分别过模り,…,恤的完全剩余系时,x2+m2x3+…+吗吗…?ー］演过模叫…久的完全剩余系。因为（叫,加2…恤）=1，由本节定理2得,㈣（x2+m2x3+…+62…mk_}xk）亦过模"4,•,mk的完全剩余系。当ホユ2,…,X«_1,X£分别过模2,め,…,"I"］,人的完全剩余系时,2有"…"I个值,且据归纳假设,若X]+m]x2HFm]・・・mk_2xk_x+"/]•••"1hド《

24=x[+m]x'2+加・_2%；_|+叫・ーw«_1X；(mod=>x,=x*(modm})；x2+m2x3+---+m2---mk_xxk=x'2+m2x'3+•••+m2•••mk_]x'k(modm2---mk)=X]=x；(modW1),x2=x2(modm2),...»xk=xk(modmk)n王=x；,x2=x2....»xk=x'k〇所以あ+m}x2+•••+m}m2---mk_ixk过模m}m2--mk的完全剩余系。3.简化剩余系与欧拉函数1.证明定理2:若。”。2，…,。出）是。（m）与m互质的整数,并且两ど対模，”不同余,则。”。2，…,〇,“）是模”!的一个简化剩余系。证明:•.•q,a2，…,为（m）两£对模〃，不同余，所以它们分别取自模团的不同剩余类,又・.,%,旳,…,外（陶恰是ク〇”）个与m互质的整数，即它们恰取自与模m互质的全部剩余类。2.若”!是大于1的正整数,a是整数，（a,/”）=l,自通过n1的简化剩余系，则エイ2|=丄。（”1）,其屮£表示展布在自所通过的一切值上的和式。"”ij2丁证明:由定理3知,す通过加的简化剩余系:囚,4，…，ル（“其中OVqVか且（《・,加）=1,而イ%;=&（i=1,2,••・。（加））。[in）加若加＞2,则。（加）必是偶数,又由（。ハ加）=1,得（加一q,加）=1,且易见加一qエa.,

25使得也用当4=1,右边共有丄。(⑼対,[m)[mJ2此即Z图屮⑼。特别地,当m=2时,。(2)=1，23.(i)证明。⑴+0(p)+…+。(バ)=パ，p质数。(ii)证明X。(の=。,其中Z展布在a的一切正整数上的和式。d/ad/a证明:⑴因为。(が)=p*-pi,仅=1,2…,a)所以。(1)+。(ロ)+…+。(ゼ)=\+(p-l)+(p--p)+---+(p"-pa~')(ii)设a=p：p2a2…pナ是a的标准分解式,则Z1=Q+P1+…+P「リ(1+P2+…+P2"コ)…(1+P*+…+P*")，d/a2。(")=(1+二(。1)+3+。(。/)>"(1+。(。«)+~+立。*"'))d/a=P/’P2%…P*4.若叫,加2,…,“是k个两两互质的正整数,ち,ら，…，気分别通过模叫,叫,…’恤的简化剩余系,则M&+Mユち+…+M爲

26通过模加叩2…恤=，”的简化剩余系,其中m=町.朋第=1,2,…，た〇证明:(数学归纳法)(1)由定理4知k=2时,结论成立;(2)设k-1时结论成立,即=恤_]=加,",.(i=l,…,んー1),。，ち,…,気ー1分别过模加],…,恤t时,ち+…+%」シ|过加’模的简化剩余系。显见(加',加・)=1,则又由定理4知,加・〃+M&通过模加'加・的简化剩余系，注意到:加”〃=(加«M)。+(?“2)ち+…+("吃ー1).-1=M昌+M&+…+M-気7所以，Mg+Mユち+…+“*"通过模m的简化剩余系。ざ4.欧拉定理・费马定理及其对循环小数的应用1、如果今天是星期ー,问从今天起再过10ザ天是星期几?解:若10ザ+1被フ除的非负最小剩余是r,则这ー天就是星期，(当r/0时是星期日).•••(107)=1,由费马定理得IC/三1(mod7),又・.TO三一2(mod7)=>1010=(-2)'°=45=4(mod6)..10,0=6Ar+4(KeZ)..IO10'0+l=106,r+4+l=104+l=34+l=5(mod7)即这一天是星期五.2、求(1237产+34片被111除的余数。解:v111=37x3..•.0(111)=0(37)^(3)=36x2=72,

271237136三1(mod37),据欧拉定理,易知',,ト=1237ピ三1(modl11)1237136=(12371)三1(mod3)...1237156三123712°(modlll)(1)又、T2371三11『+50.112371三50(modlll)故V123712=502=-53(mod111)=>v123714=532=34(modi11)nl23718三46(modlll)=>1237116=7(modlll)则123712。三34x7三16(modi11).由(1)即得.•.1237ピ三16(modlll)...1237ず+34m50(modlll)=(1237156+34)"三502'(modlll).由以上计算,知5O20=16(mod111)50s=46(mod111)....(1237屮+34ド三502t!三16x46三70(modlll).3、⑴证明下列事实但不许用定理1推论:若p是质数，ム,ら…"是整数，则(ム+%+…んア三记+ど+…グ(mod/?)〇(")由⑴证明定理1推论，然后再由定理1推论证明定理1。证明⑴对a应用数学归纳法:(1)当a=2时,按二项式展开即得(hy+h2)p=hf+h^(mod/?)(2)设a=ん时，结论成立,即(ム+る+…4)'三川+*+…始(mod/?)当a=左+1时，(ム+为+…%+ル+|)。三(ム+%+…ル)。+%三/1：'+用'+•••〃/+〃エ］(mod/?)结论成立。(〃)在⑴的结论中,令%=%=…=ん=1，即得:

28ap=a(modp)即定理1推论成立。进ー步,设m=〃ッ・・〃:',贝リ。(6)ロS-リ。r固对任一整数P,若(a,p)=l,则由上述已证性质得:ap~]=1(modp)存在んez,使。バ=1+S故伍戸ア=(1+切)'=1+。;如+—+(切)'=1+〃2/(/GZ)・・.R"ヅ三l(modp2)依此类推可得三l(modp"),即屋")三"modp").若(スか)=1,则(a,p：)=L(i=l,2,・・・s).？.)三"modガ)=>a"〃"三“mod=1,2,…$)=>a"""三1(modm),定理成立。4、证明:有理数り,。く。くん(。カ)=i表成纯循环小数的充分与必要条件是有一正数t使得同b余式10,三l(modb)成立,并且使上式成立的最小正整数t就是循环节的长度。证明:(リ必要性,若结论成立,则由定理2知(b,10)=1,令t=0(b),则据欧拉定理得10'三l(modb)；/充分性,若有正数t,满足10’三l(modb)令t为使上式成立的最小正整数,且10'=q/+l=10'a=(旳)b+a=qb+a,(q=qq)且〇<4ablO,产10'(l-1<10'—1。以下参照课本51页的证明可得:3=0.m…。,.即-可表成循环小数,但循环节的长度就是tohb

29第四章同余式p!基本概念及一次同余式例解同余式12x+15三0(mod45)解:；(12,45)=3/15••・同余多项式有3个解而原同余式为4x+5三0(modl5)4x=-5(mod15)4x4x=-20(modl5)15x+x=-20(mod15)x0=10(modl5)与/=-5(mod45)也ー样所以原同余式的3个解是x=10+15f(t=0、1,2)即司=10(mod15),x2=25(mod15),x3=40(mod15)1、求下列各同余式的解ー(i)256x.179(mod337)(zi)1215x=560(mod2755)(nz)1296x=1125(mod1935)(り•••337是素数,.-.(256,337)=1,原同余式有唯一解。先解同余式256xl(mod337)由辗转相除法,得256x104+337(-79)=1.--上述同余式的解是xm104(mod337)

30原同余式的解是xm104x179三81(mod337)(z7)v(1215,2755)=5,故先解243x当112(mod551)同(り的方法的得其解是x三200(mod551).•・原同余式的解是xm200,751,1302,1853,2404(mod2755)("り•••(1296,1935)=9,故原同余式有9个解。由!44x—125(mod215)得ス三80(mod215)原同余式的解是xm80+215]mod1935)/=0,レ82.求联立同余式x+4y-29=0(modl43)2x—9y+84三0(modl43)的解。解:据同余式的有关性质,x+4y—29三0(mod143)Jx+4ym29(mod143)2x—9y+84三0(mod143)[17y=-l(mod143)x+4y=29(mod143)y三42(modl43)x三4(modl43)为所求的解。y=42(modl43)3.(i)设m是正整数,5,加)=1.证明x=ba""0"(modin)是同余式or三シ(modm)的解(ii)设p是质数，0

31证明:(i)・・・(a,/n)=l,/.ax=b(modm)有唯一解.而据欧拉定理,得而加)三l(mod加),••，"三伙mod加)・.・〃え三い〃妣"—(modm)即x三んが")一(modm)是aス三b(modm)的解.(ii)\90(a-l)!=k(a-l)!(modp)・・.k=仇modp)日n1/1ヽa-i(P-1)・..(Pー。+1)/jヽ即ス三人(一1)———-~~—-(modp)al是の・三/?(modp)的解.设p是素数,0v。vp,证明:レハ所1(P-D(P-2)…(pー。+1)」、%=/?(-1)(moap)oal是同余方程ax=b(modp)的解。解:首先易知/一1尸(PT)(P.2)-(p-a+l)是整数,又由(a,p)=1知方程い三al。!b(modp)解唯一,故只须将ス三b(-l)a~]—-ー以セ■-————■-+(modp)代入aズ三わ(modp)验证它是同余方程的解即可。

324.设〃2是正整数,ダ是实数,く机,(。,加)=1,证明同余式ax=y(mod机),〇

3335%’三l(mod3)得M:三2(mod3)21M;三l(mod5)M|M：=l(mod3)即Af;ml(mod5)15M;三l(mod7)My=l(mod7)根据孙子定理方程组的解是xm2x35x2+1x21x3+1x115x2m233=23(mod105)注意到x0>X]>>,,,,故有限步后,必有axn=y(modm)其中04x.4r,|y|4」,即结论成立。J2.孙子定理试解下列各题:(i)H^一・数余三,七二数余二,十三数余ー,问本数。(ii)二数余ー,五数余二,七数余三,九数余四,问本数。(杨辉:续古摘奇算法(1275))。Ix=3(modl1)解:(i)依题意得(xm2(mod72)Ix=l(modl3)则据孙子定理,上述方程组有唯一解(mod11x72x13)72•73M:ml(mod11)得M：=1;由11•13M;三l(mod72)得=-1;11・72M；=l(mod13)得=-1;故原方程组的解是xm3x936+2x(-l)x143+1x(-1)x792=1730(mod10296).(ii)依题意得＜x=l(mod2)x=2(mod5)x=3(mod7)xm4(mod9)=>x=1x315+2x126+3x6x90+4x4x70=3307=157(mod630).2、(i)设回,加2,丐是三个正整数,证明:■（叫,吗）,仇,吗）］=（［叫‘啊］,”3）•（ii）设d=（叫,加2）•证明:同余式组x=b}（modm}）,x=b2（modm2）（1）

34有解的充分与必要条件是〃ムー%.在有解的情况下,适合（1）的一切整数可由下式求出:x三七2（mod［m］,〃ルD其中丸2是适合（1）的一个整数。（"リ应用（り,（"）证明同余式组xmmodmJ,i=1,2,…,k（2）有解的充分与必要条件是（町,勺）|色也）,=2,…メ,并且有解的情况下,适合（2）的一切整数可由下式求出:x=ム2..ヽ*（mod］叫,加2，…犯」）其中玉2…,・是适合（2）的ー个整数。证明：（り［的,％）,（吗,吗）卜（网，叫）施,叫）=（町,"）（め,吗）一（（g,碎））,（吗,加3））（m,,m2,m3）/FmImxzm,m2由:（加|-2，）-3）_（_团3，か2加3）3（加］,mZ）,コ（加］,加Z）（/«］,W2）,in2,m3）（rn］m2,6］mコノ麓2加3）=（（7W］,m2,加3）m1加2，（m1，m2,加3）机|团3，（〃ム，,n2，加3）加2加3）,/=（ノ叫ラ％，加ノ刀;,,n］m3，61团;，mキ叫，m2m3,血］加27n3）（机1，62）（叫m3）（机263）=（m;,加［加3，加メ〃2，机2加3）（加2，团3）=（m;，Pれ“,m2m3,m2m^,加"％,加］机;，，％ノ九2m3）/.（加］,加2,加3）（加］加ッ,加1加3,加2加3）=（，九］，，%2）（加ド加3）（加2，加3）即（加］,加3）（加2,加3）_（加］加2,加］加3,加2加3）（加］,加2,加3）（加］,加2）［（叫,加3）,（团2,加3）］=（［叫,加/,/）•（n）设⑴有解c,即c三ム（mod叫）,c=/?2（modm2）故此得シ］三ら（mod（叫,m2））,必要性成立;反之,设d|ムー灯即ム三/?2（modd）

35则由§1定理,知方程叫y三ルーム（modか2）必有解，设其解为y三%（modm2）,即叫yQ=b2-ム（modm2）令れ2=瓦+吗3则易见:%,2三ク（11^^叫）且ス］2三Z72（mod加2）即⑴有解ム2，充分性得证。进ー步,若（1）有解るy,则x=y（modm］）,x三y（modin2）即x-y是吗,叫的公倍数,当然也是［叫,叫］的倍数,/.x三y（mod［m］ノム］）故若X］ユ是⑴的ー个解,则（1）的任，解X必满足x三m式mod［加］,机2］）〇（Hi）若同余式组x=ム（mod町）,i=1,2,…,え有解,xmb.（modhi,）则イ,,,、也有解。从而由出）知必有x三鸟（mod叫）他,勺）|（4,り）,，=1,2,…,A,必要性成立。下证充分性。首先,推（i）,用归纳法易证:［（町,恤）,（吗,外）,…,（%T，S）］=（［叫,吗，…，恤ー』，"）又由（，）知ん=2时,充分性也成立;

36ix三a（mod叫）:有解エ三伙mod［叫,…,/ー］］）,ス三"ー］（modmb］）即ク三ク（mod旳）,1Vi«ん一1。设ん=b-hlimi,l

37故原同余式共有6个解是:%,=20,x2=5,x3=26,x4=11,x5=2,x6=17,(mod30)2、解同余式31x4+57x3+96x+191=0(mod225)解:・・・225=32乂52,,土一人亠…人十4x4+3x3+6x+2=0(modi2)故原同余式等价于，,‘二6x4+7x3—4x—9三o(mod52)1)先解4x4+3x^+6x+2三0(mod3)即x4-1=0(mod3)得x三土l(mod3)••・/(x)=16x3+9x2+6=>广(1)=31,3+31=3+(-1)由/'(1)ム三一I;リ=-5(mod3)=>r,=l(mod3)./.る三1+3ム三4(mod32);又由f'(一1)ら=-5(mod3)=>ん三2(mod3)x2三-1+3ら=5(mod32);即第一式有两个解る三4,X2=5(mod32).②再解g(x)=6x4+7x3-4x一9三〇(mod5)B|Jx4+2x3+x+1=0(mod5)设x=1,2(mod5).g'(x)=24x3+21x2-4.g'(1)=41.g'(2)=272,而5+415+272由41ム三0(mod5)二>ム三〇(mod5)272,2=-27(mod5)=>ら三4(mod5)・・・第二式有两个解X3三1,-3(mod52).联立x三ム(mod9)ム=4,5x=b2(mod25)Z?2=1,-3

38由孙子定理设X三100ム+126る(mod225)即原四条式有4个解是xm76,22,176,122(mod225).§4.质数模的同余式补充例子:1.解同余方程:(i)3x"+2x8+5x4-1=0(mod7)；(ii)4x20+3x12+2x7+3x-2=0(mod5)。解:(i)原同余方程等价于3x5+5x"+2x2-1三0(mod7),用x=0,±1,±2,±3代入知后者无解;(ii)原同余方程等价于2x4+2x3+3x-2=0(mod5),将x=0,±1,±2代入,知后者有解x三土1(/nod5)。2.判定(i)2x3-x2+3x-1=0(mod5)是否有三个解;(11)x6+2x5-4x2+3三〇(mod5)是否有六个解?解:(i)2x3-x2+3x-1三〇(mod5)等价于x3—3x2+4x—3三〇(mod5),又x，-x=(x3-3x2+4x-3)(x2+3x+5)+(6x2-12x+15).其中r(x)=6x2-12x+15的系数不都是5的倍数,故原方程没有三个解;(ii)因为这是对模5的同余方程,故原方程不可能有六个解。定理5若p是素数,"|p-1,P74则xn=a(modp)(14)有解的充要条件是an(mod(15)若有解，则解数为"。证明必要性若方程(14)有解Xo,则p/xo,由Fermat定理,得到

39p—1p—1an=(Xq)n=xop-1(modp)o充分性若式(15)成立,则p-1p-lp-1xp_|-x=x((xw)n-an+a"-1)p-i=(xn-a)P(x}+x(an-1),其中P(x)是关于ス的整系数多项式。由定理4可知同余方程(14)有〃个解。证毕。1、设〃!p-1,n>1,(a,p)=l.证明同余式xn=a(modp)p-1有解的充分必要条件是。"三1(modp),并且在有解的情况下就有〃个解。证明:=>)若同余式有解,令其解为x三x()(modp),设p-l=k几v(a,p)=\,:.(x0,p)=l则xop~'=xoto=1(modp)但三a(mod/?)p-1/.an=x0/,-1=1(modp);pT<=)an=1(modp)pT则由x"三〃(modp)可得x“t三三1(modp)〇它有ハー1个解。又・.,〃Ip-1令g(x)=x("X+axgf+a"バ+则X。"=(x〃ーa)g(x)三〇(modp)g(x)=0(modp)无多于（p-l）-〃个解,而xp^-1=0（modp）恰有p-l个解,xp~x-a=0（modp）必有n个解。

402.设n是整数,（a,m）=1,且已知同余式ス"三。（mod加）有一解ス三七（modm）,证明这个同余式的一切解可以表成ス=yx0（modm）其中y是同余式y"三l（modm）的解。证明:设ス三与,ス三ズ］（mod机）均是ス"三。（mod〃。的解,贝リx}n=x0"=a（modtn）,（a,m）=1,/.（x0,m）=（内,m）=1则由第三章定理3.3知,必存在y,使yx0三ル（modtn）,丁飞"三x「=Xo"（mod，%）.故原同余式的任一解可表示为x三yx°（modm）而y满足yn=l（modm）3.设（。,め）=1,セ与根是正整数,又设x（/三。（modm）,证明同余方程xk=a（modtn）的一切解x都可以表示成x三yx0（modm）,其中y满足同余方程y"三1（mod机）。解:设X|是x"三a（mod加）的任意ー个解,则一次同余方程yxQ=X\（mod加）有解y,再由yka=ykx（）k=（yxQ）k=x/三a（mod加）得y人三1（mod机）,即x1可以表示成x三yx°（modtn）,其中y满足同余方程:/三1（加od加）;反之,易知如此形式的x是x，三a（mod加）的解。

41第五章二次同余式与平方剩余§1一般二次同余式1、在同余式ザーA三O（modp。）中,若p。|A,试求出它的一切解来。解:若pa|A,则A三O（modpa）,上同余式即为y2=0（modpa）从而pa庁,即有pH及。易见,当a=2タ为偶数时,|=（3,则pH=",上同余式有解:x=-pa）,共有〃=2m+l

42由于(2。,小)=1,故2ax+わ三七(mod加)有解ス三歩(mod〃2)即有:(2aXj+b)2-(か-4ac)=O(modzn)即有:4。(。ス:+bxx+c)=0(modm)由。,即有:ax2+bxx+c三0(modni)即x三X(modm)为(1)的解,充分性得证。由充分性的讨论即知⑴的解可由(2)的解导出。§1单质数的平方剩余与平方非剩余ハ求出模z。(竺)的平方剩余与平方非剩余。d/ad解:p=37,—=18,由书中定理2知,模p=37的简化剩余系中18个平方剩余分别与序列序庁,…,ゼ例2.试判断下述同余方程是否是有解。(1)ガ三27(mod37)(2)ガ三2(mod37)(3)%2=3(modl7)中之一一数同余,而ド三1,22=4,32=9,42=16,5Z三25,6Z三36,7Z三12,8Z三27,92=1,け三26,II2=10,122三33,132=21,142三11,152=3,162三34,172三30,182=28.故模37的平方剩余为:1,3,4,7,9,10,11,12,16,21,25,26,27,30,33,34,36而其它的18个数为模37的平方非剩余:2,5,6,8,13,14,15,17,18,19,20,22,23,24,29,31,32,352.(i)应用前几章的结果证明:模p的简化剩余系中一定有平方剩余及平方非剩余存在,

43(n)证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。(位)应用(り、(")证明:模P的简化剩余系中平方剩余与平方非剩余的个数各为，・0证明:(。因为产三l(modp),1为模P的简化剩余系中的平方剩余。若模P的简化剩余系中均为平方剩余,考虑模p的绝对最小简化剩余系：ームユ,…,-1,1，...,ヒュ它们的平方为模p下的一个数：(±1)2,(土ガ,...(土£)2由假设模p的简化剩余系中任一个数与上ム二个数同余,而模p的简化剩余系中有p个数,故必有两个互相同余，矛盾。从而必有平方非剩余存在。p-\p-\(")若a,b为平方剩余,则a2=l(modp),b2=l(modp)故p-in_1(ab)2=-l(modp),(p-\)-r

44设其解是:xm2（modp）,即有:22=a(modp),^-22-a=kp=>^22-aja=kapa=0(modpaj而(2+&『=2。+c；2a-'8+C：2a-2(G)2+…+(正『=p+Qy[a,p,Q为整数(2-G『=p-Q\[a由此两式即得：（2+或）。+（2一折）“22y[a两式相乘得：(22_ザ=p2-aQ2=>p2-aQ2三0(modpff)=>p2=aQ2(modpa\取。’使得：Q。’三l(modp")则ド(。了三a(modp")故其解为x三土pQ'(modp")2.证明同余式ボ+1三0(modp),p=4m+l的解是x三土1-2…(2m)(modp)证明：首先我们证明对任意〃：p>n有下式：(«-1)!(/?-«)!=(-I)"(modp)因为(T)た三p-k(modp),于是(n-1)!=(-1/'(p-1)•••(/?-n+l)(modp)因此由威尔生定理得：

45(れー1)!(Pー〃)!三(一1)〃(P-り!三(一1)”|(—1)=(-l")(modp)其次由p=4机+1,可令〃=2m+l

46(iりp=4k+3,必有/?=8k'±l,故p=8m+73、设"是正整数,4〃+3及8〃+7都是质数,说明24n+3=l(mod8n+7)由此证明:23|2"-1,47|223-1,5031225'-10证明:当7?=8〃+7时,由本节定理1的推论知2为平方剩余,应用欧拉判别条件即有p-112=l(modp)由p=8〃+7,即得出2乐+3mi(mod8〃+7)而23=8x2+7,47=8x5+7,503=8x62+7都是形如8〃+7的素数，并且23-10.47-1.-503-1,23=,251=2222312”-1,471223-1,50312251-1。§4前节定理的证明1、求以±3为平方剩余的质数的一般表达式,什么质数以±3为平方非剩余?当它们同为1或同时为-1时,因此(-1户,ー为1,ー为-1时,n-l.a显然,当’2，为偶数，而pml(mod4)时,(-1)2=1,当是奇数,即p三一l(mod4)时，(一1)2=-1。再因为p是奇质数，关于模3我们有/?三1或p三-1,当/?三l(mod3)时,('"'=')=1

47当p三-l(mod3)时,P_这样3为平方剩余时,p为下方程组的解[p=l(mod3)[p三-l(mod3)[p=l(mod4)[p三一l(mod4)由孙子定理,即可知p三1或一l(modl2),立即当p=12〃±l时,3为平方剩余。3为平方非剩余时,p为下方程组的解fpsl(mod3),fps—l(mod3)[p=-l(mod4)p=l(mod4)由孙子定理,即可知p三5或-5(mod12),立即当p=12〃±5时,3为平方非剩余。当上ユ为偶数,(3)=1，或匕1为奇数,(3)=-1时,即2p2pp=12〃+l或12〃一5时,一3为平方剩余,类似p=12〃ー1或12〃+5,一3为平方非剩余。2、求以3为最小平方非剩余的质数的一般表达式。解:由上题知以3为平方非剩余的质数p满足:p=±5(modl2)又由3为模p的最小平方非剩余,故は)=1从而p三±l(mod8)(§3Thl推证)

48满足p=±5(modl2)的素数p形如24团+5,24/n+7,24m+17,24团+19,其中只有24〃，+7,24机+17满足p=±l(mod8)故p=24〃i+7或24〃7+17时,3为它的最小平方非剩余。§5雅可比符号1、判断§3习题1所列各同余式是否有解。略2、求出下列同余式的解数:0)x2三3766(mod5987),(“)x2=3149(mod5987)其中5987是ー个质数。やハ、,3766、,2x1883、/2,,1883,解:(z)()=()=()()59875987598759875987=748x8+3,故(一^)=一159871883等•卓5987.59873385987-'188318831883/2、,169、/169、,1883、,24、,6、=—()()=()=()=()=()188318831883169169169=(—)(—)=(―)=(―)=(-)=11691691693337665987=-1,即(り的解数为0.他)(2I丝]=1,故解数为2.'ノ15987丿1.(り在有解的情况下,应用定理1,求同余式x2三。(modp),p=4〃[+3的解。(ii)在有解的情况ド,应用§2定理1及§3定理1的推论,求同余式x2三。(modp),p=8加+5的解。解:同余式ギ三。(modp)有解,故。一三l(modp)

49(りa^P,-a=a^P*=a(modp)由p=4m+3知(am+l)2=a(modp)故x三土a(modp)即为原同余式的解。(iり由p=8m+5知丄(p—1)=4〃7+2,故ガハー1三O(modp)故(a2m+1-l)(a2ffl+,+l)s0(modp)因此(か"'+|-1)三0(modp)或(a2m+1+1)=0(modp)若前式成立,那末。.+し。三。(modp)即伍阳+り2三a(modp)若メ+|三l(modp)则原同余式的解是x三土a"M(modp)即x三土trRmodp)为原同余式的解。!若后式成立,那末ア司•。三一a(modp)由§3定理1的推论知,2是模p的平方剩余,即2^/,-')=24ffl+2=-l(modp)于是:2""2.ボ”+2三a(modp)2若。2m"三—i(modp)则原同余式的解是xs+22m+1am+1(rnodp)故x三±22m+'am+i(niodp)为原同余式的解.§6合数模的情形1.解同余式(りピ三59(modl25),(n)x=41(mod64)解:从同余式ス2三59(modl25)得x三2(mod5)

50令x=2+5ム代入x三59(mod25)得出(2+5ムア=59(mod25)从而20ム三5(mod25)即有4ム三l(mod5)故ム三4(mod5),ム=4+5ら再令x=2+5ム=2+5(4+5ら)=22+25ち代入x2三59(modl25)得出(22+25ちア三59(mod125),即100t2=-50(mod125)从而4r2三-2(mod5)故ら三2(mod5)所以x=22+25x2=72为所给同余式的解从而所有的解为:x=±72(modl25)(ii)x2=41(mod64)41=l(mod8)1故有四解记x=l+4G代入x2三41(modl6),即有:(1+4^)2=41(modl6)解得厶三l(mod2)记x=l+4(l+2厶)=5+8厶,代入x2三41(mod32)即有:(5+8r4)2=41(mod32),解得:厶三l(mod2)又记x=5+8(l+2ち)=13+16ち,代入x2三41(mod64)即有(13+16ち)一三41(mod64),解得:ち三0(mod2)故x三13(mod64)为其ー解其余三解为：x三13+32=45(mod64)x=-13(mod64)

51x=-45(mod64)2.(i)证明同余式ザ三l(mod，〃)与同余式(x+l)(x-l)三O(modzn)等价,(ii)应用(i)举出ー个求同余式ペml(modm)的一切解的方法。证明:(i)显然(ii)记m=2aガ…p：ゼ三l(mod，〃)有解,等价于方程组x2=l(mod2a),x2=l(mod=1,2,…,k有解易见デ三l(mod4)的解为x三l,3(mod4)x2=l(mod8)的解为x=l,3,5,7(mod8)ピ三l(mod2"),a〉3的解为x三1,1+2^',-1,-1-2バ(mod2。)x2=l(modp：')=>x+1三0(modp：')或x-1三0(modp：)二者不能同时成立,否则p=2矛盾故它有两个x=±l(modp：),i=1,2,…,上解,联立方程组即可求出一切解。第六章原根与指标1.设p是单质数,a是大于1的整数,证明:(i)aP-l的奇质数q是a-l的因数或是形如2px+l的整数,其中x是整数(ii)af+l的单质因数是a+1的因数或是形如2px+l的整数，其中x是整数证明(i)设q|aP-l则三l(modq)设a对模q的质数是b是质数从而b=l或p若b=l,BOap=l(modq)»故ク何ー1;若ざ=p,而同"(q)=q-l,q-1为偶数,

52记q-l=2x,则p|2x,又假设p|x故q=2px+!得证。（ii）设q为。"+1的奇质因数,则。'三一l（modq）从而円三l（modの,从而a对模q的指数団2〃.故b=l,2,p,2P之一若5=1,则。三l（modり）,从而。，三l（modり）即有1三一l（modり），不可能,故ざエ1若5=2,贝リガ三l（modり）,而〃2メl（modり）（否则6=1）故。三一l（modり）=りk+1若3=p,则。，三l（modり）,而有1三一l（modり）,不可能若ざ=2p,则由団ジ（り）二り一1,q—l=2m=>p\m记m=px,贝ljq=2px+l,得证2.设a对模m的指数是b,试证メ对模m的指数是ー巨ー（人b）证明:设メ对模m的指数为ア,则a"=（メア=l（mod/n）=団丸ア=えア=6んつy8A8（（45）（4ざ）丿（ス,ざ），反之（グ）（んf）=aゝ㈤=（グ）（ん，）三l（modm）例1求1,2,3,4,5,6对模7的指数。根据定义!直接计算,得到

53あ⑴=1,あ(2)=3,而(3)=6,あ⑷=3,あ⑸=6,あ⑹=2。例1中的结果可列表如下:a123456而(の136362这样的表称为指数表。这个表就是模7的指数表。下面是模!0的指数表:a13795io（a）14421.写出模11的指数表。解:经计算得%（1）=1,%（2）=10,ら（3）=5,5“（4）=5,即⑸=5,“（6）=10,ざ“（7）=10,由|（8）=10,心|（9）=5,①|（10）=2,歹リ表得a12345678910^n（a）110555101010522.求模14的全部原根。解:x三3,5(znod14)是模14的全部原根。1.求模29的最小正原根。解：因例29)=28=22.7,由22=2Mまl(mod29),2~~=2"まl(mod29)知2是模29的最小正原根。2.分别求模29S和模2-293的原根。解：由2是模29的原根及2?9-।=228=228，1(m〇イ29?)知2是模29コ的原根;由2是模293的原根及2是偶数知2+293是模2.29S的原根。

541.解同余方程:xい三16(mod17)。解:易得3是模17的原根,3,(i=0,1,2,…，15)构成模17的简化剩余系,歹U表为i701234563,(mod17)111391013515i15891011121314V(mod17)61614874122由上表知3g三16(mod17),设xm5y(mod17),贝リ12y三8(mod16),由此解得yim2,y2=6,九三10，J4=14(mod16),查上表得Xi三9,x2三15,わ三8,ス4三2(mod17)〇ず3指标及n次剩余1.设タ”%,…,%是タ(⑼的一切不同的质因数,证明g是模m的一个原根的充要条件是g对模m的/(»=1,2,…,〃)次非剩余。证明:必要性，设g为模m的ー个原根由42Th5知gfl(modm),i=L2,…,zn若g为模m的d次剩余，则存在へ，使得X。"=g(mod?n),(x0,m)=1又由欧拉定理V(m)=l(modw)故g外三(ス0”)%=x0^(w,)=l(mod/n),矛盾!充分性,若g不为模m的一个原根,由ざ2Th5知存在4,使得:g%=l(modin)

55设g’为模m的ー个原根,则对上式两边关于g’取指标:叭Indg三0(mod0(团))q.=>Indロg=0(modq)记!ndg=yq,,则由指标的定义即有:(g)“’三g(modm)故x三(g')’(modm)即为同余式が三g(modm)的解从而g为Z次剩余,矛盾。1.证明10是模1フ及模257(质数)的原根,并由此证明把丄,丄化成循环小数时,循环节17257的长度分别是16及256.证明:9(17)=16,它的有且只有质因子2,而从而!0不是模!7的平方剩余,由上题知10是模17的原根。9(257)=256=2',由且仅有质因子2,而故同上理10也是模257的原根。由M3§4T〃2.3的证明可知,—,一!一的循环节的长度，t,这是10关于模17,模25717257的指数，从而t=16,256证毕2.试利用指标表解同余式x”三14(mod41)解：同余式一三14(mod41)等价于:

56査表知表知4=25,故:15Indx=25(mod40)由于(15,40)=5|25,故上式由5个解,解之得:Indx=l,\5,23,31,39(mod40)査表知:原同余式的5个解为:x=29,3,30,31,7(mod41)4.设模m(m.>2)的原根是存在的，试证对模m的任一原根来说,-1的指标总是丄シ(机).证明:模m的原根存在,故m=4,「0或2pa设g为模m的ー个原根,则建0")三l(modm)从而(gユ一D(g2+l)=0(modin)(*)(り若m=4,シ(4)=2,则模m有且只有一个原根3,31s-l(modm),故ー1的指标为1=クセリ2=1若m=p",p为奇质数,则由(*)知〃(9)=0或「出2"”"+1但二者不能同时成立,否则p|(g2+I)(g2-1)=2,矛盾!—(pirn)—®(m)若p|g2-1,p\g2+1,又由(*)知~-®(m)pa\s2=>g2三1(modm),与g的指数为。(加)矛盾。,ーヘ—0(m)从而p+g2-1,p\g2+1,从而p〃|g2十］ng2=—1(modm)

57故-1的指标为(访)若加=2p-g为2ザ的原根,则g为奇数类似于(〃)的讨论,我们有P\S2T，P\g2+1-m)从而2pa\g2+1从而g2=-1(modm)故・1的指标为;0(机)〇5、设g，g]是模相的两个原根，试证:(i)indgg•indggi三T(mod(p(m))；(n)ind^a=ind^gfinda(mod(p(m))。证明:(i)由指标的定义知:g必加三g](modm)两边对原根&取指标:山4g沿三山4,g](mod(p{tn))故山ムg•山ムg]三1(modシ(机))(〃)由指标的定义知:giづ三。(modm)两边对原根g取指标:indyg=ind^a(mod(p(m))(证毕)故ind^a=ind^gfindKa(mod(p(m))。

58第九章数论函数§1.可乘函数1.设/（X）是一个可乘函数,证明ド（X）=エ也是一个可乘函数.由此说明5（a）,r（fl）是d\,x可乘函数.证明:首先我们证明:设（和ム）=1，若4跑过王的全部因子,あ跑过%的全部因子，则d=4d2跑过机〃的全部因子，事实上，因为4k-d2\x2,故4d2klム，且当クト,d2\x2,｛4,ム｝ナ｛4，4｝时，由于（あ,ム）=1，得4ムH44，反之任给ホズ内,由于（ホ,*2）=1，设（d,xj=4,（d,x2）=d2,显然d=d4,,d2\x2.因此ド（あ,ム）=X/（d）=ZZ/（d/2）d\x\x!可8d^x2立2ハ4ガ@）4kl

59矛盾!若mn>l,则对所有正态数对a,b,(a,b)=l,ab

60シ（4）=ル務=a3.试计标和式Xズ解:此题较复杂,下分数步解之:1Mobius?反演公式设『和g是两个数论函数,且“〃）=»©1（4），则g（〃）=Z"の反之亦然（l

61I"丿d

62事实上,Zf")=£fd

63d

64g(c)=，g(江〃二g(〃反之,类似可得。参见习题5及6〇②若八x）是定义在闭区间［0,1］上的函数，n正整数，记F（n）4*）,尸⑺吃喝）,化〃）=1则ド・（〃）=エの（のF4）d事实上,由①,只要证明ド（〃）=Z尸・（こ），但这几乎是明显的,因为如果分数d/nd一,2,…,ク,化成既约分数,就得到形如区的分数,这里iVaWb,b是n的ー个约数.每nnnhー个这样形式的分数都可得到・次也好一次.③记。（加）=£ゼ,（よ,血）=1,则—=V（―）2,（x,/n）=1對m七m记尸（加）ニナ（二）

65m(m+1)(2m+1)_(m+1)(2m+1)6mVx2则ド(m)=£(—)2=R-Mmm那么ドご）」（3+2%+ちJ+丄え+丄さx6xm23x6m这样由②知:粤江时）心）加“，〃X=：Z(か6)d/ad./〇d证明：设巴=ノ,即d/=〃,贝リdZWd)g(d)=X〃のZ〃c)=20(d)，(c)dfad/ac/dcd/a=Z〃c)Z0(の由推论2.3知,其内部之和只有当c=a时为1,c

66=Eg(c)Xw邑)=g(。)布由cd7.设ド(x),G(x)是定义在实数上的两个函数,并且对于任何不小于1的实数x来说:G(x)=%(与„=i〃则f(x)=y卬(〃月(モ)„=in反之,亦然.证明:MY卜］Hr£以〃)GJ)=■%)£%一)}當〃普お加〃M丫卜］丫国Y=町)£F(—)+w(2)ZF(—)+■•■+”卜］)£尸(6)(Zfm急2m”［x\记mN2k,则〃|た，并且セ遍取数目1,2,…,国,则(△')哨％)+呜)(％+*+吟~+%ア…+囁%%比较⑷,(")两式即有2%g(与=£/弓)Z%，

67上式右边除第一页（ん=1时）=F（x）,其余诺项都等于〇（推论2.3）右上式右边等于ドは）类似可证明它的逆定理成立。初等数论试卷ー、单项选择题:（1分/题x20题=20分）1.设x为实数,3为x的整数部分,贝リ（）A.[x]a}+%三ム+レ,（mod/n）;B.a}=b}(mod〃リ,〃2三る(mod〃。=ッ〃]〃2=b]b,(mod〃り;

68C.q三ム(modm,nq七三”田.(modm)；D.a2=b2(modin)=>a1三仇(modm).4.模10的一个简化剩余系是()A.〇,1,2,…，9;B.1,2,3,…，10;C.-5,-4,-3,-2,-1,0,1,2,3,4;D.1,3,7,9.7.。三わ(mod”)的充分必要条件是()A.m\a-b;B.a—h\m',C.nj|a+£>;D.a+b\in.8.设/卜)=ザ+2バ+8ス+9,同余式，(x)三0(mod5)的所有解为()A.x=l或ー1;B.x=l或4;C.x三1或-4(mod5);D.无解.9、设f(x)=anx"++。卩+へ其中q是奇数,若x三七(modp)为f(x)三0(modp)的ー个解,贝リ:()A.力三/(modp)一定为/(x)三0(mod),5>1的ー个解B.力三Z()(1110(10')。>1,一定为/(幻三0(1110(10")的ー个解C.当p不整除/(x)时,/(x)三0(modp")一定有解x三x()(modp"),其中ル=x0(modp)D・若x三%(modp")为yは)三0(modp")的ー个解,则有ル三%(modp)10.设/(尤)=a“x"++。イ+旬,其中q为奇数,。“ま0(modp),〃>p,则同余式/㈤三0(modp)的解数:()A.有时大于p但不大于n;B,可超过pC.等于pD.等于n11.若2为模p的平方剩余,则p只能为下列质数中的:()A.3B.11C.13D.23

6910.若雅可比符号（ゝ）=1,则（A.同余式バ三a（modm）一定有解,B.当（a,m）=l时,同余式ド三。（modp）有解;C.当m=p（奇数）时,同余式ズ三。（modp）有解;D.当。=p（奇数）时",同余式ズ三a（modp）有解.13.若同余式ザ三。（0！〇（12"）,二ン3,（2,。）=1有解,则解数等于（）A.4B.3C.2D.114.模!2的所有可能的指数为;（）A.1,2,4B.1,2,4,6,12C.1,2,3,4,6,12D.无法确定15.若模m的单根存在,下列数中,m可能等于:（）A.2B.3C.4D.1216.对于模5,下列式子成立的是:（）A.シ〃Z、2=2B.ind32=3C.ind35=0D.ind310=ind32+ind3517.下列函数中不是可乘函数的是:（）A.茂陛鸟斯（mobius）函数w（a）;B.欧拉函数。（a）；C,不超过x的质数的个数ア（え）；D,除数函数“a）；18.若x对模机的指数是出?，a>0,ah>0»则パ对模机的指数是（）A.aB.hC.ahD,无法确定19./（a）,g（a）均为可乘函数,则（）A./（。k（の为可乘函数;B.44为可乘函数g（a）C.f（6z）+g（a）为可乘函数:D./（。）一（。）为可乘函数

7020.设ル（。）为茂陛乌斯函数,则有（）不成立A.〃⑴=1B.〃（-1）=1C.〃（2）=-1D.〃（9）=0二.填空题:（每小题1分,共10分）21.3在45!中的最咼次n=；22.多元一次不定方程:aixl+a2x2+---+anxn=N,其中q,a2an,N均为整数,n>2,有整数解的充分必要条件是；23.有理数ユ，0

71x=l(mod5)20.解同余方程组〈y三3(mod6)z=2(mod7)21.解同余式ド三H(modl25)22.求模13的所有原根。五、证明题:(7分/题x2题=14分)39、试证:x2+2y2=z2,(x,y)=1y是偶数的整数解可写成:x=±(a2-2b2)y=2abz=ci2+2/72这里。,人＞0,(。』)=1,并且a.bー为奇数,ー为偶数。40、设a为正整数,试证:2Kd)=£(%)=ad\ad\aa其中Z表示展布在a的一切正因数上的和式。d\a六、应用题:(8分)41、求30!中末尾。的个数。参考答案:--单项选择:ABCDD；DACCB；DCAAD；BCBABo二.填空题:21.21；22.3M2,…,4)|N；23.伍,10)=1；24.%+f7n*=(),±1,12,…；(。,加)25.(p-l)!+1三0(modp),p为素数;26.1；27.a2ml(modp)；28.。(。(加))；29.g与g+p"中的单数;30.16三.简答题:31.答:命题正确。•/(2w+l)2-l=[(2nz+l)+l][(2/n+l)-l]=2w-(2w+2)=4m(w+l)而加(m+1)必为2的倍数。86页32.正确.证明见教材り7。33.在摸p的简化剩余系中与「二ユ,…(ヒ!〕同余的数是数p的平方剩余,

72p=17,；(p-l)=8,『三1,22三4,32三9,42三16,52三8,62三2,72三15,82三13故1,2,4,8,9,13,15,16为摸17的平方剩余,而3,5,6,7,10,11,12,14为摸17的平方非剩余。32.s(a)=n(l+P,+/+...+pア)=n-~卜i=\x=lPi-1r(a)=(dfj+1)(4+1)…(％+1)证明:若“の为可乘函数,则エ〃a)=fl(l+/(pJ+…叫ガ)).a\ai=\分别令/(の=。ノ(の=1,它们为可乘函数,即得出。四.计算题33.解:因为(6,93)=3|75,故原不定方程有解。又原方程即2x+3ly=25,而易见方程2x+31y=1有解*=16,.=-1〇所以原方程的ー个解是工=400,%=-25所以,原方程的一切整数解是:()x=400+31Z0,…t是整数r=-25-2t34.解：因为模5,6,7两两互质，由孙子定理得所给同余方程组关于模5x6x7=210有唯一解,分别解同余方程：42xml(mod5),35x=l(mod6),30xml(mod7),得x=3(mod5),x=-l(mod6),x=4(mod7)因此所给同余方程组的解是：x=42-3-l+35-(-l)-3+30-4-2(mod210)即：x三261三51(mod210)35.解：从同余方程ギ三1l(mod5)得xml(mod5),再从(1+5ム)2三ll(mod52),得10ム三10(mod52),因此ム三l(mod5),于是1+ム三6(mod52),是た，三”(mods?)的解,又从(6+5シ2)一三ll(mod5,得300G三一25(mod53),因此12ち三一l(mod5)

73即ら三2(mod5),所以x=6+52.2=56是所给方程的ー个解,于是所解为:x三士56(modl25)解毕。32.解:0(13)=12=22x3,g,=2,g2=3为其质因数当り=6,豊21=4,故g为模13的原根的主要条件是:g6まl(modl3),g41(mod13)用g=l,212逐一验证,得：2,6,7,11为模13的原根,因为。(12)=4,故模13原根只有4个,即为所求。五、证明题:39.证明:易验证所给的解为原方程的解,因y为偶数,原方程可化为:/ロ(z+xZ-xYfz+xZ-xy但〔ア，テハテ，テ尸〔-2-，-2_Z〔_2-，-2_JWO.z)=1,所以(上,—)=122由书中引理，我们可假设=a,=b22显然a>b,(a,b)=l,于是X=a2—b2,z=a2+b2,y=2ab因子为奇数,所以。,b一定是ー为奇,ー为偶,证毕40.证明:假定《,ム为a的所有正约数，那末

74—，-,二也是a的所有正约数,于是44〉（d）=Z的）d/ad/a4再因为在。的完全剩余系中任一数。的最大公约数必定是4,一,ム中某一个数,而完全剩余系中与a的最大公约数为4的数有。（二）,所以:4证毕六.应用题:41.解:5在30!中的最高次箒==6+1+0=7M旦吉、ル育「30］「301「30］「30］「302在30!的取咼次哥=—++ア+デ=15+7+3+1+0=2610=2x5,故30!的末尾有7个零。2007年4月广东省高等教教育育自学考试初等数论试卷ー、单项选择题。（本大题共15小题,每小题2分，共30分）1.-36,420,48三个数的公因数是（）A.±1,±3,±4,±5,±6,±12B.±1,±2,±3,±4,±6,±,12C,土2,土3,土4,±601,2,3,4,5,6,122.设a,biZ（整数集），p是素数,且p!。わ。则（）Aa,b中恰有一个是p的倍数B.a,b中没有p的倍数C.a,b中必有一个是p的倍数D.a,b都是p的倍数3.设a,b是非零整数,d=（a,b）,则下列成立的是（）

754.设ス伍c#?Z且。〃わv=1,则对于任意diZ+（正整数集）（）B.(ad.bd)=abdD,餾ル，=dB・御”ーセ}D.«〃}=・セ}B.21x+15y+65z=72D.100%+2Qy+45z=32B.(a,b)=(b,m)D.(a-b,m)=(a,m)B.{1,2,37,8}D.{29,14,-2,2,19,,19,7,8}B.2720°l(mod25)D.3541°l(mod41)A.(ad.bd)=dC.（ad,bd）=ab5.对任意实数。,必有（）A•麻=窗+16.下列不定方程中,有整数解的是()A.27x+75y+33z=48C.42x-7Qy+14z=337.设a,b挝Z,mZ+,a久modm*"()A.(a,b)=(a,m)C.(a,m)=(m,b)8.下列集合中,是模15的简化剩余系的是()A.{1,2,3,5,7,8,11,13}C.{1,4,8,7,11,13,14}9.下列同余式中成立的是()A.3648°l(mod49)C.472°4(mod72)10.设同余式ax°仇modm）有解,则下述断语中正确的是（）A.该同余式有模m的m-1个解B.在模m的ー组完全剩余系中,有（b,m）个数满足该同余式C.在模m的•组完全剩余系中,有（a,m）个数满足该同余式

76D,在模m的ー组完全剩余系中,有（ab,m）个数满足该同余式10.设素数p>2,a,b分别是模p的平方剩余和平方非剩余,则下列成的是（）A.ab是模p的平方非剩余Ca2b是模p的平方剩余11.设对模m的指数为に,则（）A.k\mC.k卜13.若模m的原根存在,贝リm"J"能是（）A.15的倍数6.8I的2倍B.ab2是模p的平方非剩余D.メが是模p的平方非剩余B.m卜D,%レ（/n）B.16的倍数D.42的倍数14.若x对模m的指数是ab,a>O,b>O,则ー对模m的指数是（）A.abtnB.bC.a-bD.a15.设g是模m的一个原根,c=ノ（in）.K是模c的ー个非负完全剩余系,则L=セ’JiK｝是（）A.模m的ー个完全剩余系B模m的ー个简化全剩余系C模c的ー个完全剩余系D模c的ー个简化全剩余系二.填空题（本大题共10,每小题2分,共2分）16.设a=2,创3、5コ?112,62Z创5ム7413?,c=3创5，7513、则野,c=17.若a,b,是两个整数,b>0,设“,则用m,r表达的b除a的带余式是18.--的标准分解中7的指数为32!19.有理数ユ（0

7718.设a,b,c,m都是整数,姉。ac(modm),则当时,b°c(modm).19.设か=p^'p°'Lpノ丹为互异的奇素数(i=l,2k),(a,m)=1,则同余式x?°a(modm)有解时,解数为t20.设m是偶数,则模m有原根的充分必要条件是t21.设a对模m的指数为L则メ0l(mod/n)成立的充分必要条件是t22.若。1,4,L,a,是与m互素的t个整数,则由或巴,%,!^,《)°(mod;(m))三、计算题。(本大题共4题,第26,27小题各5分,第28,29小题各7分,共24分)26.解不定方程方程+57y=531的整数解.27.求3对模52的指数.卜02(mod3)28.解同余方程组レ°3(mod4)卜03(mod5)29.对哪些奇素p,3是模p的二次剩余?四、应用题(本题10分)30.今天是星期三,试求经过，=(2〇〇2〇〇3+IZMy999天后是星期几?五、证明题(本大题共2题，每小题8分，共30分)31.求证3是模17的原根.32.已知383是素数,求证ゼ。219(mod383)有解。2007年4月广东省高等教教育育自学考试初等数论试题答案及评分参考ー、单项选择题1—5BCDAB6—10ACDBC11—15ADCDB16.24仓較56仓ザip於夕17.a=b;l旨（或〃=bm+br）

7818.1219010)=1或存在一个正整数t,使得10I。l(modの成立。20.SJ-')(?；'-p2"ハ)L(pJ-p：T)或m(l--)(1--)L(1--)PiPiP*21(a,m)=122.2423.m=2,4或2p",其中a为正整数,p为素数24.ホ25.inda]+idna、+L+idnaj三、计算题26.解:(123,57)=3331,所以方程有整数解。化简方程得41+1%=177.(1分)解得41=19?2319=3?61于是1=19-3?619-(41-19仓期6=41?(6)+1913故41?(6?177)19创16177=177知方程有特解へ=-6?177,九!3177(3分)一般解为Ia=0,北!，2,L)(5分)卩=13?17741/27、解:j(52)=24,24的正因数为1,2,3,4,6,8,12,24(2分)依次检验：31汉3,329ア汉27,3429(mod52)36°l(mod52)(4分)故3对模52的指数是6

79（5分）

8028、解:啊=3,加2=4,%=5,m=60Mx=20M=15,M,=12而M；=2,M；=3,M；=3(3分)故此同余组的解为x捍220?23创153+3创123(mod60)°23(mod60)(7分)29、解:显然/P5,由二次互反律,有Ch&l!p01(mod3)V1»如P2(mod3)(-リl-1»如p3(mod4)い力)所以Iわ?小声介(P°l(mod3)或汉2・1(mod3)(、分)しVKmod4)いし汉3-l(mod4)いノJノ部p1(mod12)所以只有当p罕(mod12)时,3是模p的二次剩余(7分)四、应用题30、解：要求「模フ的余数200汉4(mod7),125(mod7)由欧拉定理46汉l(mod7)51(mod7)(2分)于是2〇〇2期汉42°°343336春452(mod7)(5分)12'00?510056'16#54542(mod7)(7分)

81于是再过•天就是星期日（10分）五证明题31、证:求得，（17）=16=2,,其不同素因数只有2（2分）（4分）jホ7ゝ而32=38汗16l（modl7）（6分）所以3是模17的ー个原根（8分）32、证:219=373,于是鶴協施盜。分，由二次互转律（7分）所以（8分）勸9亠，t—士=1故同余方程ザ。219（mod383）有解