《初等数论》第三版习题解答
- 格式：doc
- 大小：5.13 MB
- 文档页数：77
《初等数论》习题解答（第三版）
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，(,)|abb
00(,)|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 / 77 1102222bbqqtabsababt
若 0b，则令11,22qqstabsab，则同样有2bt，综上所述，存在性得证．
下证唯一性
当b为奇数时，设11abstbst则11()ttbssb
而111,22bbttttttb 矛盾 故11,sstt
当b为偶数时，,st不唯一，举例如下：此时2b为整数
11312(),,22222bbbbbbbtt
§2 最大公因数与辗转相除法
1．证明推论4.1
推论4.1 a，b的公因数与（a，b）的因数相同．
证：设d是a，b的任一公因数，d|a，d|b
由带余除法
111222111111,,,,,0nnnnnnnnnnabqrbrqrrrqrrrqrrrrb
(,)nabr
d|1abq1r， 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[||,||,,||]naaa
3．设1110nnnnaxaxaxa
（1）
是一个整数系数多项式且0a，na都不是零，则（1）的根只能是以0a的因数作分子以na为分母的既约分数，并由此推出2不是有理数．
证：设（1）的任一有理根为pq，(,)1,1pqq。则 《初等数论》习题解答（第三版）
6 / 77 1110()()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）算出10010a
（2）10内的质数为：2，3，5，7 《初等数论》习题解答（第三版）
7 / 77 （3）划掉2，3，5，7的倍数，剩下的是100内的素数
将不超过100的正整数排列如下：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
2．求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是任意两个正整数，且
