《初等数论(闵嗣鹤)》课后习题解答2012修改版.pdf 63页

'《初等数论》习题解答（修改版）（茂名学院WeiXLI）第一章整数的可除性§1整除的概念·带余除法1．证明定理3定理3若aa，a，，都是m得倍数，qq，q，，是任意n个整数，则12n12nqaqaqa是m得倍数．1122nn证明：aa,,a都是m的倍数。12n存在n个整数pp,,p使apma,,,pmapm12n1122nn又qq,,,q是任意n个整数12nqaqaqa1122nnqpmqpmqpm1122nn()pqqpqpm1122nn即qaqaqa是m的整数1122nn2．证明3|(nn1)(2n1)证明nn(1)(2n1)nn(1)(n2n1)nn(1)(n2)(n1)(nn1)又nn(1)(n2)，(n1)(nn2)是连续的三个整数故3|(nn1)(n2),3|(n1)(nn1)3|(nn1)(n2)(n1)(nn1)从而可知3|(nn1)(2n1)3．若axby是形如axby（x，y是任意整数，a，b是两不全为零的整数）的数中最小00整数，则(axby)|(axby)．001/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）证：ab,不全为0在整数集合Saxbyxy|,Z中存在正整数，因而有形如axby的最小整数axby00xy,Z，由带余除法有axby()axbyqr,0raxby0000则r()xxqa()yyqbS，由axby是S中的最小整数知r00000axbyaxby|00axbyaxby|（xy,为任意整数）axbyaax|,|byb000000axby|(,).ab又有(,)|aba(,)|abb00，(,)|abaxby故axby(,)ab00004．若a，b是任意二整数，且b0，证明：存在两个整数s，t使得||babst,||t2成立，并且当b是奇数时，s，t是唯一存在的．当b是偶数时结果如何？33bbbb证：作序列,,bb,,0,,,,则a必在此序列的某两项之间2222qq1即存在一个整数q，使bab成立22qq()i当q为偶数时，若b0.则令s,tabsab，则有22qqqb0abstababbt2222qqb若b0则令s,tabsab，则同样有t222qq11()ii当q为奇数时，若b0则令s,tabsab，则有222/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）bbqq11tabsabab0t2222qq11b若b0，则令s,tabsab，则同样有t综上所述，存在性222，得证．下证唯一性当b为奇数时，设abstbst则ttbs()sb1111bb而tttt,ttb矛盾故sstt,1111122b当b为偶数时，st,不唯一，举例如下：此时为整数2bbbbb3b1b2(),t,t1122222§2最大公因数与辗转相除法1．证明推论4.1推论4.1a，b的公因数与（a，b）的因数相同．证：设d是a，b的任一公因数，d|a，d|b由带余除法abqrb,11rqr,,r122n2rqrr,n11nnnrq,nn10rrrrbn1nn11(,)abrnd|abqr，d|brqr，┄,d|rrqr(,)ab,11122n21nnn即d是(,)ab的因数。3/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）反过来(,)ab|a且(,)ab|b，若dab|(,),则dadb|,|，所以(,)ab的因数都是ab,的公因数，从而ab,的公因数与(,)ab的因数相同。2．证明：见本书P2，P3第3题证明。3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）．解：有§1习题4知：babZb,,0,st,,Z使abstt,||。，2||tbst,，使bsttt,||,,如此类推知：11111222stt,,;tstnnn21nnns,t,;ttstn1n1n1nn1n1|tt|||||tb||nn12且||tn21nn2222而b是一个有限数，nN,使t0n1(,)(,)(,)(,)abbttttt(,tt)(,0)tt，存在其求法为：112nn1nn(,)(,abbabs)(absb,(abss))1(76501,9719)(9719,7650197197)(8468,97198468)(1251,846812516)(3,1)1logb4．证明本节（1）式中的nlog24/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）证：由P3§1习题4知在（1）式中有rrrbnn1210rr，而rnn121nnn12222bnlogblogb1,2b，nblog，即nn22log2log2§3整除的进一步性质及最小公倍数1．证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件axbt1．证明必要性。若(,)1ab，则由推论1.1知存在两个整数s，t满足：asbtab(,)，asbt1充分性。若存在整数s，t使as+bt=1，则a，b不全为0。又因为(,)|,(,)|abaabb，所以(,|abasbt)即(,)|1ab。又(,)0ab，(,)1ab2．证明定理3定理3aa,,a|a|,|a|,|a|12nn12证：设[,aa,,a]m，则ami|(1,2,,)n121ni1∴|a||mi(n1,2,,)又设[|a|,|a|,,|a|]mi1122n则mm|。反之若|am||，则am|，mm|21i2i212从而mm，即[,aa,,a]=[|a|,|a|,,|a|]1212n12n2nn13．设axaxaxa（1）nn110是一个整数系数多项式且a，a都不是零，则（1）的根只能是以a的因数作分子以a为0n0n分母的既约分数，并由此推出2不是有理数．p证：设（1）的任一有理根为，(,)1,pqq1。则q5/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）ppnnp1aa()aa()0nn110qqqnnnn11apapqapqaq0（2）nn110nnnn11由(2)apapqapqaq，nn110n所以q整除上式的右端，所以qap|，又(,)1,pqq1，nn所以(,qpqa)1,|；nnnnn11又由（2）有apapqapqaqnn110nn因为p整除上式的右端，所以Paq|，(,)1,pqq1，所以(,)1,qppa∴|0np故（1）的有理根为，且paqa|,|。0nq2假设2为有理数，xx2,20，次方程为整系数方程，则由上述结论，可知其有有理根只能是1,2，这与2为其有理根矛盾。故2为无理数。p另证，设2为有理数2=,(,)1,pqq1，则q2p22222222,2qp,(pq,)(2,qp)q12q22但由(,)1,pqq1知(pq,)1，矛盾，故2不是有理数。§4质数·算术基本定理1．试造不超过100的质数表解：用Eratosthenes筛选法（1）算出10010a（2）10内的质数为：2，3，5，76/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）（3）划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002．求82798848及81057226635000的标准式．3解：因为8|848，所以8|,AAB827988488103498562，3又8|856，所以8|B，BC812937322，2又4|32，所以4|C，CD432343322又9|（3+2+3+4+3+3），所以9|D，DE9359373，又9|（3+5+9+3+7），所以9|E，E939933又399331331311853所以A2311；33432同理有81057226635000235711172337。3．证明推论3.3并推广到n个正整数的情形．推论3.3设a，b是任意两个正整数，且ap12ppn，0，ik1,2,,，12nibp12ppn，0，ik1,2,,，12ni则(,)abp12ppk，[,]abp12ppk，12k12k7/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）其中min(,)，min(,)，ik1,2,,iiiiii证：min(,)，0,0iiiiiii∴ppii|i,i|pp(ik1,2)iiiikkkk∴ppii，ppii.iiiiii11ii11∴pp12pabk|(,)，又显然(,)|abpp12pk12k12k∴pp12pabk(,)，同理可得pp12pabk[,]，max{,}12k12kiii推广设app1112p1k,ap21p22p2k,,apn12pnpnk112k212knk12(其中p为质数jka1,2,,,为任意n个正整数in1,2,,,0)，则jiijppi12ipik(,aa,,a),min{},j1,2,,k12k12nijij1inppi12ipik[,aa,,a],max{},j1,2,,k12k12nijij1in4．应用推论3.3证明§3的定理4（ii）证：设app1211pkk，bppp，1212kk其中p1,p2,,pk是互不相同的素数，i，i（1ik）都是非负整数，有(,)abpp11pk，min{,}，1ik，12kiii[,]abpp11pk，max{,}，1ik。12kiiikkk由此知(a,b)[a,b]=piipmin{i,}max{ii,}ipii=ab；从而有[,]abab．iiii1i1i1(,)abn５．若21是质数（n>1），则n是2的方幂．k证：（反证法）设n2(ll为奇数），kkkkkn2l2l22(1)l2(l2)则2121(2)1(21)[221]8/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）kk22ln∵121(2)121，n∴21为合数矛盾，故ｎ一定为２的方幂．§5函数[x],{x}及其在数论中的一个应用1．求30！的标准分解式．解：30内的素数为2，3，5，7，11，13，17，19，23，29303030303022222324251543102330303030103101433323433303030610755523530303030404，2027772111111230303030202，202131313213131323030101，117171721919232923145422∴30!23571113171923292．设n是任一正整数，是实数，证明：n(i)n11n(ii)nnn证：(i)设[]m.则由性质II知mm1,9/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）所以nmnnmn,[]n所以nm[]nnmn，所以mm1，又在ｍ与ｍ+１之间只有唯一整数ｍ，n[]n所以[][]m．nkk1(ii)[证法一]设{},0,1,2,kn,1,nn则kn{}kn1,[n]k[]ik1ii①当ikn1时,{}1,[][];nnnikii②当ikn时,2{}1,[][]1;nnn11n[][][]nnn1n1kn11ii[][][]i00nininkn(nk)[]k([]1)nk[]n1i[][n]i0n[证法二]n1i令fn()[][],i0nn111if()[][n1]f()nni0n111if()[][n1]f()nni01f()是以为周期的函数。n10/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）又当[0,1),()000,时fRf,()0，n11即[][]n。i0n[评注]：[证一]充分体现了常规方法的特点，而[证二]则表现了较高的技巧。3．设，是任意二实数，证明：(i)[][][]或[]1(ii)[2][2][][][]证明：（i）由高斯函数[x]的定义有[]r,[]s,0r1;0s1。则[][]rsrs,1当rs0,[时][][]当rs0,[时][][]1故[][][][或]1[][]（ii）设[]x,[]y,0xy,1，则有0{}{}2xy下面分两个区间讨论：①若01xy，则[xy]0，所以[][][]，所以[2][2][2[]2][2[]2]xy2[]2[]2([][])xy2[]2[][][][][][][][]②若12xy，则[xy]1，所以[][][]1。所以11/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）[2][2][2[]2][2[]2]xy2[]2[]2([][])xy2[]2[]2([][1xx])xy1[][][][]22([][xx])2[]2[]1[][][]（ii）（证法2）由于，对称，不妨设{}{}[2][2][2([]{})][2([]{})]2[]2[][2{}][2{}]2[]2[][{}{}][][]([][][{}{}])[][][[]{}[]{}][][][]4.(i)设函数在闭区间QxR上是连续的，并且非负，证明:和式表示平面区域QxR，0()yfx内的整点（整数坐标的点）的个数.(ii)设p，q是两个互质的单正整数，证明：(iii)设，T是区域内的整点数，证明：(iv)设，T是区域，，内的整点数，证明：12/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）证明：(略)5.设任一正整数，且，p是质数，，证明：在的标准分解式中，质因数p的指数是其中.证明：在的标准分解式中，质因数p的指数有限，即，所以而第二章不定方程§2．1习题1、解下列不定方程a)15x25y100b)306x360y63013/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）解：a)原方程等价于：35xy20显然它有一个整数解xy10,2，00xt105故一般解为(t0,1,2,)yt23b)原方程等价于：1720xy35显然它有一个整数解xy735,63500xt73520故一般解为(t0,1,2,)yt635172、把100分成两份，使一份可被7整除，一份可被11整除。解：依题意即求711xy100的正整数解，解得xy8,400xt811一般解是：(t0,1,)yt47但除t0外无其他正整数解，故有且只有10056443、证明：二元一次不定方程axby,Na0,b0,(,)1abNN的非负整数解为或1ababN证明：当N0时，原方程没有整数解，而10故命题正确abNN当N0时，原方程有且只有一个非负整数解0,0而011abab因为ab,1所以nn1原方程有整数解xy,,y(1)q,,qNx,(1)q,,qN0001nn1021a其中qqq,,,,q，由于ab0，故xy,中一正一负，可设xy0,0123n00bxxbt0原方程的一般解是：t0,1,yyat0xy00要求xbt0,yat0t，00bay0y0y0仅当是整数时，才能取t，否则taaa14/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）故这个不等式的整数解个数T是：x0y0x0y0当是整数时T11babaNNxy00因而T1abbaaby0x0y0x0y0当不是整数时T1ababaxy00Nba因而所以()mabxy001baxxbt0证明2：二元一次不定方程axby=N的一切整数解为，tZ，于yyat0yxyxN0000是由x0，y0得t，但区间[],的长度是，故此区间内的abababNN整数个数为[][]或1。abab：4、证明：二元一次不定方程axbyNab,(,)1,a1,b1，当Nabab时有非负整数解，Nabab则不然。证明：先证后一点，当Nabab时，原方程有非负整数解xy,00则d(mm,).12bx1,ay1x1bky,1ahk,1,h10000abkhabkh,2，这是不可能的。次证，当N>ab-a-b时，因(a，b)=1，故原方程有整数解（x，y），一般解是xx0bt(t0,1,)00yy0atyx00要求x-bt0，yat0t会证明存在满足这个不等式的整数tt可取使000abxbtr(0rb)于是对于这个t有：00015/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）xb1xbtrbt1而00ba111yaty(xb1)(byaxaba)(Naba)()abababa1000000bbbby0yat0t000a这就证明了当Nabab时，原方程有非负整数解．1．证明定理2推论。推论单位圆周上座标都是有理数的点（称为有理点），可以写成222222abababab()(),,或22222222abababab的形式，其中a与b是不全为零的整数。ln22222证明：设有理数xy，（m0）满足方程xy=1，即ln=m，mm222222于是得l=2abd，n=(ab)d，m=(ab)d或l=(ab)d，m=2abd，22222222ababababm=(ab)d，由此得(x,y)=()(),,或。反之，22222222abababab22代入方程xy=1即知这样的点在单位圆周上。2222．求出不定方程x3yz,(,)1,xyx0,y0,z0的一切正整数解的公式。222解：设不定方程x3yz,(,)1xy有解则222(1)3/z-x或3/z+x因为3yzx(zxzx)()3/(zxzx)()3/zx或3/z+x2222zx2zxx3yzyzx或者yzx33得3/zx或3/zx以下不妨设3/zx16/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）222②xz,1，设(x,z)则d,d/x,d/zyd/3z,x222若,3/,dy9/x,9/z9/3y3/3/xy,与xy,1矛盾!222这样3,dddy1///3yyd而dx//,1dxyd③zxzx,12或，设tzxzx,/()(tzx)2zxx，t/(zx)(zx)2zt/2.2xz2即tt12或zx④若zxzx,1,,1,zx则322zx从而3yyzxzxzx3zx22由引理可设a,zxb,yab3从而，为证得xz,为整数，xz,1,22必须有a，b均为奇数，且3abzxzxzxzx⑤若zxzx,2,1,1226222yzxzx从而3yzxzx262zx2zx2y2222设a,b,ab,即x3ab,y2abz,3ab，622其中ab,为一奇一偶，且有ab,12224．解不定方程：x3y=z，x>0，y>0，z>0，(x,y)=1。22解：设(zx,zx)=d，易知d=1或2。由(zx)(zx)=3y得zx=3da，222zx=db，y=dab或zx=db，zx=3da，y=dab，a>0，b>0，(a,b)2222|b3a|b3a=1。(ⅰ)当d=1：x，yab，z，a>0，b>0，(a,b)=2222221，3|b，a,b同为奇数；(ⅱ)当d=2：x=|b3a|，y=2ab，z=b3a，a>0，b>0，(a,b)=1，3|b，a,b一奇一偶。反之，易验证(ⅰ)或(ⅱ)是原17/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）不定方程的解，且x>0，y>0，z>0，(x,y)=1。2243．证明不等式方程xyz,xy,1,x0,y0,/zx的一切正整数解．22442222可以写成公式:xab4(),aby∣abab6∣，zab其中a0,b0,ab,1,,ab一单一双2222证明:由定理1知道原方程的解是x2cdy,,,zcdcdcd0,,cd1，且c，d为一奇一偶，22其中，c2abd,,0,abab,1ab，且a，b为一奇一偶．22442222所以xab4(),aby∣abab6∣，zab是原方程的正整数解22(x0,y0,z0,xy,1,2/,x且ab是奇数，原方程正整数的解有:2222442222000,，，0,，aa，a,0,a4ab(ab),(ab6ab),(ab)，44222222(ab6ab),4ab(ab),(ab),2246．求方程xy=z的满足(x,y)=1，2x的正整数解。224解：设x，y，z是xy=z的满足(x,y)=1，2x的正整数解，则x=2ab，2222222y=ab，z=ab，a>b>0，(a,b)=1，a,b一奇一偶，再由z=a222222222b得a=2uv，b=uv，z=uv或a=uv，b=2uv，z=uv，224422u>v>0，(u,v)=1，u,v一奇一偶，于是得x=4uv(uv)，y=|uv6uv|，22z=uv，u>v>0，(u,v)=1，u,v一奇一偶。反之，易验证它是原不定方程的整数解，且x>0，y>0，z>0，(x,y)=1，2x。其中正负号可任意选取．第三章同余1同余的概念及其基本性质18/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）1、证明（i）若(modm)1k1kxy(modm)、i=1，2，、、、，kii则x11xykky(modm)11kk11,,1k,,k1,,k特别地，若ab（modm），i=0，1，,n则iinn11nnaxaxabxbxb（modm）nn10nn10(ii)若ab(modm)，k0,(modakbk),mkabm（iii）若ab(modm)，d是a，b及m的任一正公因数，则(mod),bdd(iv)若ab(modm)，dmd,0.则ab(modd)．证明：（i）据性质戊，由xy(mod),mi1,2,,.kii得xiiy(mod),mi1,2,,,kii进一步，则x11xkkByy(mod)m1kk11kk1最后据性质丁，可得：x11xkkyy（modm）11kk11,,1k,,k1,,k(ii)据定理1，ab(modm)mab,k0,mkkab()kakb又据定理1，即得kakb(modmk).（iii）据定理1，ab(modm)mab,即a-b=ms(sz)abmabmdabmd,,,0,s，即s,dddddabm仍据定理1，立得(mod),bdd(iv)据定理1，ab(modm)aamss,(z),19/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）又dm,,,mdttz故abmsdstst(),z,ab(mod).dnn12、设正整数aa10aa10,0a10nni10ni试证11整除的充分且必要条件是11整除(1).aii1证明：101(mod11),由上题(i)的特殊情形立得nn1nn1aaa10a10aa(1)a(1)(mod11)nn10nn10niaa(1)i(mod11),i0ni11aa11(1)i．i03．找出整数能被37，101整除有判別条件来。解：10001(mod37)kk1故正整数aa1000a1000a,0a1000kki10k立得37aa37i.i01001(mod101).ss1故设正整数ab100b100b,0b100"，ss10isi立得101ab101(1)i.i0324、证明641｜218证明：∵2256mod64120/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）162∴225665536154mod641322∴2154237161mod64132即641∣21n22n5、若a是任一单数，则a1mod2，n1证明：（数学归纳法）设am2122（1）n1时，a2mmm14111mod8，结论成立。（2）设nk时，结论成立，即：kk22kk222mmt110mod22112，tzk1kkkk22222而a1a1a1a1a122kk22222tt22kk43tt22kk31tt221k30mod2故nk1时，结论也成立；∴n1时，结论也成立。n2n+2证明：若2|a，n是正整数，则a1(mod2)。(4)设a=2k1，当n=1时，有223a=(2k1)=4k(k1)11(mod2)，即式(4)成立。设式(4)对于n=k成立，则有kk2k+22k+2a1(mod2)a=1q2，其中qZ，所以k12k+22k+3k+3a=(1q2)=1q21(mod2)，其中q是某个整数。这说明式(4)当n=k1也成立。由归纳法知式(4)对所有正整数n成立。21/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）i1535625；ii115806634解：i153562535713；22ii115806623713101§2剩余类及完全剩余系stts1、证明xupv，up0,1,2,,1，ts是模p的一个完全剩余类。sttsss证明：显然对uv,的不同取值，x共有ppp个值，故只需证这样的p个值，关于模p的两两互不同余。ststs若upvupvpmod1122stsu1u2pv1v2modpststp∣uu，即uumodpuu121212stststpv1pv2modpv1v2modpv1v2∴uu或vv时，1212ststsupvupvmodp．结论成立。11222、若mm,m,,是k个两两互质的正整数，xx,,x,分别通过模mm,m,,的完全剩12k12k12k余类，则MxMxMx1122kk通过模mmmm的完全剩余系，其中mmM，ik1,2,,12kii证明：（数学归纳法）（1）根据本节定理3，知k2时，结论成立。（2）设对整数k1，结论成立，即若mm,,,m两两互质，令12k1""""sMxMxMx，当xx,,,x分别通过模mm,,,m的完全剩1122kk1112k112k1"余系时，s必过模"""mmm...m的完全剩余系，其中mMmi(1,2...k1)。12k1ii22/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）现增加m,使(,mm)1(ik1,...1)，kik"令MMmk(1,...1)，mMmm...m，mmMmm...mikkkk121kkk12则易知(,mm,...,m)(mM,)1，12kkk"再令xMxms，kkk"当x过模m的完全剩余系，s过模M的完全剩余系时，据本节定理3，x必过模kkkmmMmm...m的完全剩余系，即对k结论成立。kk12kn1313、（i）证明整数HHH,...1,0,1,...,()中每一个整数有而且只有一种方法表示成31nn13x3x...3xx.............nn10的形状，其中xi1,0,1(n0,1,...)；反之，中每一数都HH且,。i（ii）说明应用n1个特别的砝码，在天平上可以量出1到H中的任意一个斤数。n1证明：（i）当xi1,0,1(n0,1,...)时，过模2H13的绝对最小完全剩余系，也就是in1表示HH,中的21H个整数，事实上，当x1,0,1时，共有3个值，且两两互不相i等，否则n"nn1"n""13x3x...3xx3x3x...3xxnn110nn110nn"1"""3(xx)3(xx)...3(xx)xxnnn1n11100""3|xxxx.0000此即nn1"2""3(xx)3(xx)...(xx)0nnn11n"""3|xxxx...xx1111nnn1nn131又的最大值是33...31H31nn1最小值是33...31H所以，结论成立。23/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）rr2na（ii）特制n1个砝码分别重1,3,3,...,3斤，把要称的物体di及取-1ii11di的砝码放在天平的右盘，x取1的砝码放在左盘，则从（i）的结论知，当x取适当的值时，iinn1可使T3xxxx3...3.之值等于你所要称的物体的斤数H。nn104、若mm,,...,m是K个两两互质的正整数，xx,,...x分别过模mm,,...,m的完全剩余系，12k12k12k则xmxmmx,...mm,,...,mx.................11212312kk通过模mm,,...,m的完全剩余系。12k证明：（数学归纳法）（1）K2时，xx,分别过模mm,的完全剩余系时，1212xmx共有mm个值，且若11212xmxxmx(modmm)mx(x)xx(modmm)112112121221112xxmxx11，且xxm(mod)111222m1xx，xx，即k2时结论成立；1122（2）设当xx,,分别过模mm,,的完全剩余系时，2k2kxmxmmmx过模mm的完全剩余系。22323kk12k因为(mm,m)1，由本节定理2得，12kmx()mxmmx亦过模mm的完全剩余系。12232kk12k当xx,,,x,x分别过模mm,,,m,m的完全剩余系时，12kk112kk12有mmm个值，且据归纳假设，12k若xmxmmxmmx1121k2k11k1kxmxmmxmmx(modmm)1121k2k11k1k1k24/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）xx(modm)；xmxmmx1112232kk1xmxmmx(mod)mm223212kkkxxm(mod)，xxm(mod)，…，xxm(mod)111222kkkxx，xx，…，xx。1122kk所以xmxmmmx过模mmm的完全剩余系。112121kk12k3．简化剩余系与欧拉函数1．证明定理2：若aa,a,,是()m与m互质的整数，12()m并且两对模m不同余，则aa,,,a是模m的一个简化剩余系。12()m证明：aa,,,a两对模m不同余，所以它们分别取自模m的不同剩余类，12()m又aa,,,a恰是()m个与m互质的整数，即它们恰取自与模m互质的全部剩余类。12()m2．若m是大于1的正整数，a是整数，(,)1am，通过m的简化剩余系，a1则()m，其中表示展布在所通过的一切值上的和式。m2证明：由定理3知，通过m的简化剩余系：aa,,,a，其中0＜a＜m且(,)1am，12()miiaaii而（im1,2,()）。mm若m＞2，则()m必是偶数，又由(,)1am，i得(mam,)1，且易见maa，iiiamaamaiiii故1mmm25/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）aaa12a()m所以.mmmmaimaiaj左边每一项都存在另一项()ij，mmmaiaj1使得1，右边共有()m对，mm2a1此即()m。m2a1特别地，当m=2时，(2)1,。m23．（i）证明(1)()p(p)p，p质数。(ii)证明()da，其中展布在a的一切正整数上的和式。dadakkk1证明：（i）因为()ppp，(k1,2,)所以(1)()pp()21=1(p1)(pp)(pp)=p(ii)设app12pk是a的标准分解式，12k则d(1pp12)(1pp)(1ppk)，1122kkda()d(1()p(p1))(1(p)(pk))11kkda=pp12pk12k=a4．若mm,,,m是k个两两互质的正整数，,,,分别通过模mm,,,m的简化剩12k12k12k余系，则MMM1122kk26/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）通过模mmmm的简化剩余系，其中mmMi,1,2,,k。12kii证明：（数学归纳法）（1）由定理4知k=2时，结论成立；（2）设k-1时结论成立，即mmmmMi(k1,,1)，,,,分别过11kii121k模mm,,时，11kMMM112211kk过m模的简化剩余系。显见(,mm)1，则又由定理4知，mM通过模mm的简化剩余系，注意到：kkkkkm(mM)(mMmM)()kkkk1k1k2211MMM1122kk11所以，MMM通过模m的简化剩余系。1122kk4．欧拉定理费马定理及其对循环小数的应用1010１、如果今天是星期一，问从今天起再过10天是星期几？1010解：若101被7除的非负最小剩余是r，则这一天就是星期r（当r0时是星期日）．61071，由费马定理得101mod7，10105又102mod710244mod610106K4KZ10106K444101101101315mod7即这一天是星期五．2856２、求1237134被111除的余数。解：111373.11137336272，12371361mod3736据欧拉定理，易知123711mod1113621812371123711mod327/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）56201237112371mod111（１）2又12371111501237150mod1112242故123715053mod111123715334mod1118161237146mod111123717mod1112056则1237134716mod111．由（１）即得1237116mod11128565628123713450mod111123713450mod111．208由以上计算，知5016mod1115046mod111．285628123713450164670mod111．３、()i证明下列事实但不许用定理１推论：若p是质数，hh,,h是整数，则12apppp(h1h2haa)modh1h2hp。()ii由()i证明定理１推论，然后再由定理１推论证明定理１。证明()i对a应用数学归纳法：1当a2时，按二项式展开即得ppp(h1h2)h1h2modp2设ak时，结论成立，即pppp(h1h2hkk)h1h2hmodp当ak1时，ppp(hhhh)(hhh)h12kk112kk1pppph1h2hkkh1modp结论成立。()ii在()i的结论中，令hhh1，即得：12apaamodp即定理１推论成立。28/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）s进一步，设mpp1s，则mpp1i11siii1固对任一整数p，若ap,1，则由上述已证性质得：p1p1ap1mod存在kz，使akp1pp1pp12故()a=1kp1Ckpkp1pl（lz）ppp12ap1modp11app依此类推可得(a)1modpp,即1mod．piii若am,1，则ap,1,isi1,2,.ap1modiiammpiisam，定理成立。1modi,1,2,1moda4、证明：有理数,0abab,,1表成纯循环小数的充分与必要条件是有一正数t使得同bt余式101modb成立，并且使上式成立的最小正整数t就是循环节的长度。证明：i必要性，若结论成立，则由定理2知（b，10）=1，t令t=b,则据欧拉定理得101modb；2ta充分性，若有正数t，满足101modbt令t为使上式成立的最小正整数，且10=qb11t10aaqba11qbaq,aqtatt1且0qab10101101。bb以下参照课本51页的证明可得：a..a=0.aa1t.即可表成循环小数，但循环节的长度就是t。bb29/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）第四章同余式1基本概念及一次同余式例解同余式12x150mod45解：（12，45）=315同余多项式有3个解而原同余式为4x50mod154x5mod154420mod15x15xx20mod15x10(mod15)与x5(mod45)也一样00所以原同余式的3个解是xt1015（ｔ＝０、１、２）即x10(mod15)，x25(mod15)，x40(mod15)1231、求下列各同余式的解30i256x179mod33725ii1215x560mod2755iii1296x1125mod1935i337是素数，256,3371，原同余式有唯一解。30先解同余式256x1mod33725由辗转相除法，得256104337791上述同余式的解是x104mod337原同余式的解是x10417981mod337ii（1215，2755）=5，故先解30/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）30243x112mod55125同i的方法的得其解是x200mod551原同余式的解是x200,751,1302,1853,2404mod2755iii(1296，1935)=9，故原同余式有9个解。30由144x125mod215得x80mod21525原同余式的解是xtt80215mod1935,0,18.xy4290(mod143)2．求联立同余式的解。2xy9840(mod143)解：据同余式的有关性质，xy4290(mod143)xy429(mod143)2xy9840(mod143)17y1(mod143)xy429(mod143)x4(mod143)为所求的解。y42(mod143)y42(mod143)3．(i)设m是正整数，(,)1am．证明()1mxbam(mod)是同余式axb(mod)m的解(ii)设p是质数，0ap，证明a1(p1)(pa1)xbp(1)(mod)a!是同余式axb(mod)p的解．证明:(i)(,)1am，axb(mod)m有唯一解．()m而据欧拉定理，得am1(mod)，31/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）axb(mod)m()1mm()1aaxbam(mod)()1m即xbam(mod)是axb(mod)m的解．(ii)0(,)1apap即axb(mod)p有唯一解又a个连续整数之积必被a!所整除，a1(ppa1)(1)故可令abk(1)a!a1则b(1)ppa(1)ka(1)(1)!aa12(1)b(1)(p1)(pa1)b(1)(ap1)!(mod)2(a1)即b(1)(a1)!ka(1)!(mod)pkb(mod)pa1(p1)(pa1)即xbp(1)(mod)a!是axb(mod)p的解．设p是素数，02）的原根是存在的，试证对模m的任一原根来说，1的指标总是()m．2证明：模m的原根存在，故m=4，p或2p()m设g为模m的一个原根，则gm1(mod)11()mm()从而(g221)(gm1)0(mod)i若m=4，42，则模m有且只有一个原根3，131(mod)m，m故1的指标为1211若mp，p为奇质数，则由知1()mpg|1290或11()mm()但二者不能同时成立，否则pg|(221)(g1)2，矛盾!11()m()m若pg|21,|pg21,又由（*）知1()mpg|21()mg21（modm），与g的指数为()m矛盾。111()m()m()m从而p|g21,pg|12，从而pg|121()mg21（modm）57/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）1故-1的指标为()m。2()iii若mp2，g为2p的原根，则g为奇数类似于()ii的讨论，我们有11()m()mp|g21，pg|121()m从而2|pg121()m从而g21（modm）1故-1的指标为()m。25、设g，g是模m的两个原根，试证：1()iindgindg1（mod()m）；gg11()iiindaindginda（mod()m）。gg1g1证明：()i由指标的定义知：indgg1gg（modm）1两边对原根g取指标：1indgg1indgindg（mod()m）gg111故indgindg1（mod()m）gg11()ii由指标的定义知：indagga1（modm）1两边对原根g取指标：indaindgg1inda（mod()m）gg故indaindginda（mod()m）。（证毕）gg11g58/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）第九章数论函数§1．可乘函数1．设fx()是一个可乘函数，证明Fx()fd()也是一个可乘函数．由此说明sa(),a()是dx可乘函数．证明：首先我们证明：设(,xx)1，若d跑过x的全部因子，d跑过x的全部因子，则ddd12112212""跑过mn的全部因子，事实上，因为dx,dx，故ddxx，且当dx,dx，112212121122""""d12,,12ddd时，由于(,xx12)1，得dd12dd12，反之任给dxx12，由于(,xx12)1，设(,)dxd，(,dx)d，显然ddd,,dxdx．因此1122121122Fxx(,12)fd()12fdd()dxx1211dxdx22fdfd()()12dxdx1122fd()1fd()2FxFx()()12dx11dx22故Fx()为一个可乘函数．(此为65页)若fx()x，它为可乘函数．，且Fa()fa()Sa()．da若fx()1，它为可乘函数，且Fa()fd()()a．da故Sa(),a()为可乘函数．2．设fx()是一个定义在一切正态数的函数，并且Fx()fd()是一个可乘函数，证明dxfx()是可乘函数．证明：反证，假设fx()不是可乘函数，则存在一对正态数mn,,(,)1mn，使得fmn()fmfn()()，于是我们可以选择这样一对mn,，使得mn最小．若mn1，则f(1)f(1)(1)f，即f(1)1，又F(1)()fa(1)f，Fx()为可乘函数，故有fF(1(1)1d1矛盾！59/63 《初等数论》习题解答（修改版）（茂名学院WeiXLI）若mn>1，则对所有正态数对a,b,(a,b)=1,ab