第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a 是m 得倍数．证明： 12,,n a a a 都是m 的倍数。
存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m又12,,,n q q q 是任意n 个整数1122n n q a q a q a 1122n n q p m q p m q p m1122()n n p q q p q p m即1122n n q a q a q a 是m 的整数 2．证明 3|(1)(21)n n n证明 (1)(21)(1)(21)n n n n n n n (1)(2)(1)(1)n n n n n n又(1)(2)n n n ，(1)(2)n n n 是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n3|(1)(2)(1)(1)n n n n n n从而可知3|(1)(21)n n n3．若00ax by 是形如ax by （x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ．证： ,a b 不全为0在整数集合 |,S ax by x y Z 中存在正整数，因而有形如ax by 的最小整数00ax by,x y Z ，由带余除法有0000(),0ax by ax by q r r ax by则00()()r x x q a y y q b S ，由00ax by 是S 中的最小整数知0r00|ax by ax by00|ax by ax by （,x y 为任意整数） 0000|,|ax by a ax by b 00|(,).ax by a b 又有(,)|a b a ，(,)|a b b 00(,)|a b ax by 故00(,)ax by a b4．若a ，b 是任意二整数，且0b ，证明：存在两个整数s ，t 使得||,||2b a bs t t成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？证：作序列33,,,,0,,,,2222b b b bb b 则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b 成立 ()i 当q 为偶数时，若0.b 则令,22q qs t a bs a b，则有 02222b q q qa bs t ab a b b t若0b 则令,22q qs t a bs a b，则同样有2b t ()ii 当q 为奇数时，若0b 则令11,22q q s t a bs a b，则有若 0b ，则令11,22q q s t a bs a b，则同样有2b t，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t 则11()t t b s s b 而111,22b bt t t t t t b矛盾 故11,s s t t 当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d 是a ，b 的任一公因数， d |a ，d |b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b(,)n a b rd |1a bq 1r ， d |122b r q r ，, ┄d |21(,)n n n n r r q r a b ,即d 是(,)a b 的因数。
反过来(,)a b |a 且(,)a b |b ，若|(,),d a b 则|,|d a d b ，所以(,)a b 的因数都是,a b 的公因数，从而,a b 的公因数与(,)a b 的因数相同。
2．证明：见本书P2，P3第3题证明。
3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）．解：有§1习题4知：,,0,,,a b Z b s t Z 使,||2ba bs t t。
， 11,s t ，使1112||,||,,22t bb s t t t 如此类推知： 21,,;n n n n n n s t t t s t 11111,,;n n n n n n s t t t s t且1221||||||||||2222n n n n n t t t b t而b 是一个有限数，,n N 使10n t1121(,)(,)(,)(,)(,)(,0)n n n n a b b t t t t t t t t t ，存在其求法为：1(,)(,)(,())a b b a bs a bs b a bs s(76501,9719)(9719,7650197197)(8468,97198468)(1251,846812516)(3,1)14．证明本节（1）式中的log log 2bn证：由P3§1习题4知在（1）式中有 12112102222n n n n n n r r r br r，而1n r 1,22nn b b， 2log log log 2b n b ，即log log 2b n §3 整除的进一步性质及最小公倍数1．证明两整数a ，b 互质的充分与必要条件是：存在两个整数s ，t 满足条件1ax bt ． 证明 必要性。
若(,)1a b ，则由推论1.1知存在两个整数s ，t 满足：(,)as bt a b ，1as bt充分性。
若存在整数s ，t 使as+bt=1，则a ，b 不全为0。
又因为(,)|,(,)|a b a a b b ，所以(,|)a b as bt 即(,)|1a b 。
又(,)0a b ，(,)1a b 2．证明定理3定理3 1212,,||,||,||n n a a a a a a 证：设121[,,,]n a a a m ，则1|(1,2,,)i a m i n ∴1|||(1,2,,)i a m i n 又设122[||,||,,||]n a a a m 则21|m m 。
反之若2|||i a m ，则2|i a m ，12|m m 从而12m m ，即12[,,,]n a a a =122[||,||,,||]n a a a 3．设1110n n n n a x a x a x a （1）是一个整数系数多项式且0a ，n a 都不是零，则（1）的根只能是以0a 的因数作分子以n a 为不是有理数．证：设（1）的任一有理根为pq，(,)1,1p q q 。
则1110()(0n n n n p p pa a a a q q q111100n n n n n n a p a p q a pq a q （2）由11110(2)n n n n n n a p a p q a pq a q ，所以q 整除上式的右端，所以|n n q a p ，又(,)1,1p q q ， 所以(,)1,|n n q p q a ；又由（2）有11110n n n n n n a p a p q a pq a q因为p 整除上式的右端，所以0|n P a q ，(,)1,1p q q ，所以(,)1, |n n q p p a ∴ 故（1）的有理根为pq，且0|,|n p a q a 。
220x x ，次方程为整系数方程，则由上述结论，可知其有有理根只能是1,2 为无理数。
=,pq(,)1,1p q q ，则2222222222,2,(,)(2,)1p q p p q q p q q但由(,)1,1p q q 知22(,)1p q 不是有理数。
§4 质数·算术基本定理 1．试造不超过100的质数表 解：用Eratosthenes 筛选法（110 a（2）10内的质数为：2，3，5，7（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 1002．求82798848及81057226635000的标准式．解：因为8|848，所以38|,827988488103498562A A B ， 又8|856，所以8|B ，3812937322B C ， 又4|32，所以4|C ，243234332C D又9|（3+2+3+4+3+3），所以9|D ，29359373D E ， 又9|（3+5+9+3+7），所以9|E ，93993E 又3399331331311 所以8532311A ；同理有3343281057226635000235711172337 。
3．证明推论3.3并推广到n 个正整数的情形． 推论3.3 设a ，b 是任意两个正整数，且1212n n a p p p ，0i ，1,2,,i k ， 1212n nb p p p ，0i ，1,2,,i k ， 则1212(,)k k a b p p p ，1212[,]k ka b p p p ，其中min(,)i i i ，min(,)i i i ，1,2,,i k 证： min(,)i i i ， 0,0i i i i∴|,|i i i i i i i i p p p p (1,2)i k∴11iikki ii i p p，11iikki ii i p p.∴ 1212|(,)k k p p p a b ，又显然1212(,)|k ka b p p p ∴1212(,)k k p p p a b ，同理可得1212[,]k k p p p a b ，max{,}i i i推广设11112112k k a p p p ,22122212k k a p p p ,1212,n n nk n k a p p p(其中j p 为质数1,2,,,i j k a 为任意n 个正整数1,2,,,0ij i n )， 则1212121(,,,),min{},1,2,,i i ik k n ij ij i np p p a a a j k1212121[,,,],max{},1,2,,i i ik k n ij ij i np p p a a a j k4．应用推论3.3证明§3的定理4（ii ）证：设12111212k k k k a p p p b p p p ，，其中p 1, p 2, , p k 是互不相同的素数， i ， i （1 i k ）都是非负整数，有11111212(,)min{,}1[,]max{,}1k kk i i i k i i i a b p p p i k a b p p p i k ，，，，，。