《初等数论》第三版习题解答

《初等数论》习题解答（第三版）1/77第一章整数的可除性§1整除的概念·带余除法1．证明定理3定理3若12naaa，，，都是m得倍数，12nqqq，，，是任意n个整数，则1122nnqaqaqa是m得倍数．证明：12,,naaa都是m的倍数。存在n个整数12,,nppp使1122,,,nnapmapmapm又12,,,nqqq是任意n个整数1122nnqaqaqa1122nnqpmqpmqpm1122()nnpqqpqpm即1122nnqaqaqa是m的整数2．证明3|(1)(21)nnn证明(1)(21)(1)(21)nnnnnnn(1)(2)(1)(1)nnnnnn又(1)(2)nnn，(1)(2)nnn是连续的三个整数故3|(1)(2),3|(1)(1)nnnnnn3|(1)(2)(1)(1)nnnnnn从而可知3|(1)(21)nnn3．若00axby是形如axby（x，y是任意整数，a，b是两不全为零的整数）的数中最小整数，则00()|()axbyaxby．《初等数论》习题解答（第三版）2/77证：,ab不全为0在整数集合|,SaxbyxyZ中存在正整数，因而有形如axby的最小整数00axby,xyZ，由带余除法有0000(),0axbyaxbyqrraxby则00()()rxxqayyqbS，由00axby是S中的最小整数知0r00|axbyaxby00|axbyaxby（,xy为任意整数）0000|,|axbyaaxbyb00|(,).axbyab又有(,)|aba，(,)|abb00(,)|abaxby故00(,)axbyab4．若a，b是任意二整数，且0b，证明：存在两个整数s，t使得||,||2babstt成立，并且当b是奇数时，s，t是唯一存在的．当b是偶数时结果如何？证：作序列33,,,,0,,,,2222bbbbbb则a必在此序列的某两项之间即存在一个整数q，使122qqbab成立()i当q为偶数时，若0.b则令,22qqstabsab，则有02222bqqqabstababbt若0b则令,22qqstabsab，则同样有2bt()ii当q为奇数时，若0b则令11,22qqstabsab，则有《初等数论》习题解答（第三版）3/771102222bbqqtabsababt若0b，则令11,22qqstabsab，则同样有2bt，综上所述，存在性得证．下证唯一性当b为奇数时，设11abstbst则11()ttbssb而111,22bbttttttb矛盾故11,sstt当b为偶数时，,st不唯一，举例如下：此时2b为整数11312(),,22222bbbbbbbtt§2最大公因数与辗转相除法1．证明推论4.1推论4.1a，b的公因数与（a，b）的因数相同．证：设d是a，b的任一公因数，d|a，d|b由带余除法111222111111,,,,,0nnnnnnnnnnabqrbrqrrrqrrrqrrrrb(,)nabrd|1abq1r，d|122brqr，┄,d|21(,)nnnnrrqrab,即d是(,)ab的因数。《初等数论》习题解答（第三版）4/77反过来(,)ab|a且(,)ab|b，若|(,),dab则|,|dadb，所以(,)ab的因数都是,ab的公因数，从而,ab的公因数与(,)ab的因数相同。2．证明：见本书P2，P3第3题证明。3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）．解：有§1习题4知：,,0,,,abZbstZ使,||2babstt。，11,st，使1112||,||,,22tbbsttt如此类推知：21,,;nnnnnnstttst11111,,;nnnnnnstttst且1221||||||||||2222nnnnntttbt而b是一个有限数，,nN使10nt1121(,)(,)(,)(,)(,)(,0)nnnnabbttttttttt，存在其求法为：1(,)(,)(,())abbabsabsbabss(76501,9719)(9719,7650197197)(8468,97198468)(1251,846812516)(3,1)14．证明本节（1）式中的loglog2bn《初等数论》习题解答（第三版）5/77证：由P3§1习题4知在（1）式中有12112102222nnnnnnrrrbrr，而1nr1,22nnbb，2logloglog2bnb，即loglog2bn§3整除的进一步性质及最小公倍数1．证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件1axbt．证明必要性。若(,)1ab，则由推论1.1知存在两个整数s，t满足：(,)asbtab，1asbt充分性。若存在整数s，t使as+bt=1，则a，b不全为0。又因为(,)|,(,)|abaabb，所以(,|)abasbt即(,)|1ab。又(,)0ab，(,)1ab2．证明定理3定理31212,,||,||,||nnaaaaaa证：设121[,,,]naaam，则1|(1,2,,)iamin∴1|||(1,2,,)iamin又设122[||,||,,||]naaam则21|mm。反之若2|||iam，则2|iam，12|mm从而12mm，即12[,,,]naaa=122[||,||,,||]naaa3．设1110nnnnaxaxaxa（1）是一个整数系数多项式且0a，na都不是零，则（1）的根只能是以0a的因数作分子以na为分母的既约分数，并由此推出2不是有理数．证：设（1）的任一有理根为pq，(,)1,1pqq。则《初等数论》习题解答（第三版）6/771110()()0nnnnpppaaaaqqq111100nnnnnnapapqapqaq（2）由11110(2)nnnnnnapapqapqaq，所以q整除上式的右端，所以|nnqap，又(,)1,1pqq，所以(,)1,|nnqpqa；又由（2）有11110nnnnnnapapqapqaq因为p整除上式的右端，所以0|nPaq，(,)1,1pqq，所以(,)1,|nnqppa∴故（1）的有理根为pq，且0|,|npaqa。假设2为有理数，22,20xx，次方程为整系数方程，则由上述结论，可知其有有理根只能是1,2，这与2为其有理根矛盾。故2为无理数。另证，设2为有理数2=,pq(,)1,1pqq，则2222222222,2,(,)(2,)1pqppqqpqq但由(,)1,1pqq知22(,)1pq，矛盾，故2不是有理数。§4质数·算术基本定理1．试造不超过100的质数表解：用Eratosthenes筛选法（1）算出10010a（2）10内的质数为：2，3，5，7《初等数论》习题解答（第三版）7/77（3）划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002．求82798848及81057226635000的标准式．解：因为8|848，所以38|,827988488103498562AAB，又8|856，所以8|B，3812937322BC，又4|32，所以4|C，243234332CD又9|（3+2+3+4+3+3），所以9|D，29359373DE，又9|（3+5+9+3+7），所以9|E，93993E又3399331331311所以8532311A；同理有3343281057226635000235711172337。3．证明推论3.3并推广到n个正整数的情形．推论3.3设a，b是任意两个正整数，且1212nnappp，0i，1,2,,ik，1212nnbppp，0i，1,2,,ik，则1212(,)kkabppp，1212[,]kkabppp，《初等数论》习题解答（第三版）8/77其中min(,)iii，min(,)iii，1,2,,ik证：min(,)iii，0,0iiii∴|,|iiiiiiiipppp(1,2)ik∴11iikkiiiipp，11iikkiiiipp.∴1212|(,)kkpppab，又显然1212(,)|kkabppp∴1212(,)kkpppab，同理可得1212[,]kkpppab，max{,}iii推广设11112112kkappp,22122212kkappp,1212,nnnknkappp(其中jp为质数1,2,,,ijka为任意n个正整数1,2,,,0ijin)，则1212121(,,,),min{},1,2,,iiikknijijinpppaaajk1212121[,,,],max{},1,2,,iiikknijijinpppaaajk4．应用推论3.3证明§3的定理4（ii）证：设12111212kkkkapppbppp，，其中p1,p2,,pk是互不相同的素数，i，i（1ik）都是非负整数，有11111212(,)min{,}1[,]max{,}1kkkiiikiiiabpppikabpppik，，，，，。由此知(a,b)[a,b]=min{,}max{,}111iiiiiiiikkkiiiiiippp=ab；从而有[,](,)ababab．５．若n21是质数（n1），则n是2的方幂．证：（反证法）设2(knll为奇数），则2222(1)2(2)2121(2)1(21)[221]kkkkknllll《初等数论》习题解答（第三版）9/77∵22121(2)121kkln，∴21n为合数矛盾，故ｎ一定为２的方幂．§5函数[x],{x}及其在数论中的一个应用1．求30！的标准分解式．解：30内的素数为2，3，5，7，11，13，17，19，23，292234530303030302222215431023323430303030333310310145233030306107555