下载文档原格式
第一章 整数的可除性§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 nq a q a q a ∴+++1122n n q p m q p m q p m =+++1122()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 n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若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 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b b b 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 r =∴d '|1a bq -1r =， d '|122b r q r -=，┄, d '|21(,)n n n n r r q r a b --=+=,即d '是(,)a b 的因数。
第三章 同余§1习题（P53）1． 证明定理2及性质庚、壬 01定理2 若11(mod )k k A B m αααα≡(mod )i i x y m ≡ ，1,2,,i k =则1111k k kk A x x αααααα≡∑ 1111(mod )k k kk B y y m αααααα∑证：由(mod )i i x y m ≡ ⇒戊(mod )ii ii x y m αα≡11kkx x αα⇒≡戊11(mod )k k y y m αα111kk k A x x αααα⇒≡ 戊111(mod )k kk B y y m αααα1111kk kkA x x αααααα⇒∑≡ 丁1111(mod )k k kk B y y m αααααα∑02庚证：（i ）(mod )a b m ≡∵ 由P48定理1m a b km ka kb ⇒−⇒−，0(mod )km ak bk mk >⇒≡ （ii ）设1a a d =，1b b d =，1m m d =0m >∵，100d m >⇒>(mod )a b m ≡∵ 111()m a b dm d a b ⇒−⇒−111111(mod )(mod a b mm a b a b m d d d⇒−⇒≡⇒≡2． 设正整数101010nn a a a a =+++ 010i a <-，试证11/a 的充要条件是011(1)ni i i a =−∑。
证：由101(mod 11)10(1)(mod 11)i i ≡−⇒≡−10(1)(mod 11)10(1)(mod 11)nni iii i i i i i i a a a a ==⇒≡−⇒≡−∑∑01110(1)nnii i i i i a a ==⇒−−∑∑于是11a 011(1)ni i i a =⇔−∑3． 找出整数能被37，101整除的判别条件来。
01 由10001(mod 37)≡ 及1010001000n n a a a a =+++ ，01000i a <-，由上面证明之方法得3737ni i a a =⇔∑02 由1001(mod 101)≡− 及10100100n n a a a a =+++ 0100i a <- 由上面证明之方法可得：101101(1)ni i i a a =⇔−∑4． 证明3264121+证：由7640251(mod 641)=×≡− 及4456252(mod 641)−=−≡3272577252122252(25)∴+≡×−×=−742173212(525)2(5)(521)≡−×−≡×−×+32173(521)(25)1≡×+≡×= 3(1)10(mod 641)≡−+≡3264121∴+5． 若a 是任一单数，则221(mod 2)nn a +≡(1)n . 证明：当n =1时，322/1a − 2(21)14(1)k k k +−=+∵ 假定2221nn a +−，则有1222222211()1(1)(1)n nn n na a a a a +⋅−=−=−=−+由2221nn a +−，221na +（∵a 是单数，∴21na +是双数）∴1321n n a a ++−，即1221(mod 2)n n a ++≡6． 应用检查因数的方法求出下列各数的标准分解式（i ）1535625 （ii ）1158066 解：（i ）由215356252561425252457=×=×由3245718+++=，324573819391=×=× 由91713=×43153562553713∴=⋅⋅⋅（ii ）由311586627+++++=，11580663386022=×33862221++++=，3860223128674=×由7128674546−+=，128674718382=×718382364−+=，1838272626=×262621313213101=×=×× 22115806637131012∴=⋅⋅⋅⋅§2习题（P57）1． 证明s t x u p v −=+，u =0，1，…，1s t p −−，v =0，1，…，1t p −，t s -，是模s p 的一个 完全剩余系。
第一章整数的可除性教学目的和要求（1）深刻理解整除、最大公因数、最小公倍数、质数的概念，正确理解带余数除法（Euclid算法）和算术基本定理的意义及作用。
（2）掌握并能直接运用辗转相除法求最大公因数，掌握幼拉脱斯展纳Eratosthenes筛法造质数表的原理。
（3）熟练掌握整除、质数、最大公因数和最小公倍数的基本性质，理解并掌握函数[x]、{x}的概念和基本性质，会求n!的标准分解式（n较小）。
本章重点是整除的概念和性质，整除理论是初等数论的基础，学好本章可为学习后继章节打下良好的基础。
习题要求P4：1，2，3 ；P9：1，2；P14：1,2；P19：5；P23：1,2,3。
第一节整除的概念·带余数除法定义1设a，b是整数，b≠ 0，如果存在整数q，使得a = bq成立，则称b整除a或a被b整除，此时a是b的倍数，b是a的因数（约数或除数），并且记作：b∣a；如果不存在整数q使得a = bq成立，则称b不能整除a或a不被b整除，记作：b|/a。
定理1下面的结论成立：(1) a∣b，b∣c⇒a∣c；（传递性）(2) m∣a，m∣b⇒m∣(a±b)(3) m∣a i，i = 1, 2, , n⇒m∣a1q1+a2q2+ +a n q n，此处q i∈Z（i = 1, 2, , n）。
（证明留给学生自己）注：① a ∣b ⇔ ±a ∣±b ；② b ∣a ⇒ bc ∣ac ，此处c 是任意的非零整数；③ b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；b ∣a 且|a | < |b | ⇒ a = 0。
④因式分解 a n -b n =(a-b )M 1, n ∈Z a n +b n =(a+b )M 2, 2n定理1(带余数除法) 设a 与b 是两个整数，b >0，则存在唯一的两个整数q 和r ，使得 a = bq + r ，0 ≤ r < b 。
