第一章 整数的可除性

主要内容:1．1.整除的概念1．2.带余数除法1．3.最大公因数的理论与性质1．4.最小公倍数的理论与性质1．5.辗转相除法1．6.素数与合数1．7.算术基本定理1．8.高斯函数[x]与{x}及其应用1.1.1 整除的定义与性质1.整除的定义定义设a，b∈Z，b≠ 0，若存在整数c，使得a = bc成立，则称a被b整除（或b整除a），并称a是b的倍数，b是a的约数（因数或除数），记为b∣a；如果不存在整数c使得a = bc成立，则称a不能被b整除，记为b|/a。

在整除的定义中应特别注意：（1）0不整除任何整数（即0不能作除数），但任何非零数整除0；在记号“b∣a”中蕴含着b≠ 0成立。

（2）显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数（平凡因子），a的除±1，±a外的约数称为非平凡约数（或真因数）。

（3）能被2整除的整数称为偶数，不能被2整除的整数称为奇数。

若整数a ≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

2.整除的性质定理1.1.1 设,,a b c ,m,n 是整数,下面的结论成立：(ⅰ) a ∣b ，b ∣c ⇒ a ∣c （整除的传递性）；(ⅱ) a ∣b ⇔ ±a ∣±b ，即a ∣b ⇔ |a |∣|b |;m ∣a , n ∣b ⇒ mn ∣ab ；(ⅲ) 若b ∣a ，且b ∣c ⇒ b ∣(ka+lc)（其中k , l 是任意的整数）；一般地，若m ∣a i ，i = 1, 2, , n ⇒ m ∣（q 1a 1 + q 2a 2 + + q n a n ）， 此处q i （i = 1, 2, , n ）是任意的整数；(ⅳ) b ∣a ⇔ bc ∣ac ，此处c 是任意非零的整数；(ⅴ) 若b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；若b ∣a ，且|a | < |b | ⇒ a = 0；若b ∣a ，且a ∣b ，a >0, b>0, 则a =b.证明 (ⅰ)由整除定义及|a b ，|,b c 知: 存在两个整数12,k k 使得:12,b ak c bk ==, 因此12()c k k a =, 由于12k k 是整数, 故 |a c .(ⅱ) — (ⅳ)的结论类似可证. 证毕.注 为了证明“|b a ”，最为基本的手法是将a 分解为b 与某个整数之积，即a bc =，其中c 是整数.这样的分解, 常常通过某些代数式的分解因式公式中取特殊值而产生. 如：（Ⅰ）若n 是正整数，则1221()();n n n n n n a b a b a a b ab b -----=-++++（Ⅱ）若n 是正奇数，则在上式中以（b -）代换b 得:1221()().n n n n n n a b a b a a b ab b ----+=+-+-+例1 证明十进制整数5001001个能被十进制整数1001整除.证明 由分解因式公式(Ⅱ),有500513171*********=+=+个（）33163153101[(10)10101],=+-+-+（）（）所以, 31011001+=能整除5001001个.证毕想一想:此题目能变形推广吗?推广后的一般形式是什么?例2 若n 是正奇数，则8∣（n 2 - 1）.证明 设n = 2k + 1，()k Z ∈，则 n 2 - 1= (2k + 1)2 - 1 = 4k (k + 1).由于k 和k + 1中必有一个是偶数，所以8∣（n 2 - 1）. 证毕注 由此得到一个重要且常用的结论：“任何奇数的平方与1的差都能被8整除”.诸如此类的还有，“任何整数的平方被4除的余数为0或1，被3除的余数为0或1; 任何整数的立方被9除的余数为 0，1或8”等，解题后可及时总结归纳, 并灵活运用这些性质.例3 设n 是奇数，则16∣(n 4 + 4n 2 + 11).解 因为 n 4 + 4n 2 + 11 = (n 2 - 1)(n 2 + 5) + 16.由于n 是奇数,有8∣(n 2 - 1)，且2∣(n 2 + 5),故16∣(n 2 - 1)(n 2 + 5).从而16∣(n 2 - 1)(n 2 + 5)+16,即16∣(n 4 + 4n 2 + 11).例4 设,m n 为正整数，且0m n >≥, 证明: 22(21)|(21)n m +-. 证明 由于0m n >≥, 故10m n --≥. 于是:112222(2)m n m n +--=在公式(Ⅰ)中，令 122n a +=, 1b =，则:11111111221222222222(2)(2111[(2)(1)2)2]n m n n m n m m n n n n +--+--+++------++=+=+-所以 122(21)|(21),n m +-- 又 1222(221(21),1)n n n ++-=-因此 122(21)|(21).n n ++-由定理1.1.1中 (ⅰ),即整除的传递性知：22(21)|(2).1n m+- 证毕． 注1 在此例中，直接证明“22(21)|(21)n m +-”不易入手，因此尝试选择适当的“中间量（1221n +-）”，使之满足定理1.1.1中 (ⅰ)的条件，再利用整除的传递性导出所要的结论.注2 在此例中，形如“221n n F =+()n N ∈”的数称为费马数.当0m n >≥时, 费马数满足: |(2)n m F F -，即存在整数t ，使得2m n F t F -=⋅.例5 设正整数n 的十进制表示为: 10(09,0,0)k i k n a a a a i k a =≤≤≤≤≠，且110()k k S n a a a a -=++++，证明：9|n 的充要条件是9|()S n .证明：由于101010k k n a a a =⨯++⨯+,110()k k S n a a a a -=++++，1()(101)(101)(101)k i k i n S n a a a ∴-=-+-++-, 对于所有的0,i k ≤≤ 有9|(101),i -由整除的性质知上式右端k 个加项中每一项都是9的倍数，由定理1.1.1之(ⅲ)知它们的和也被9整除，即9|(()),n S n - 从而 9|9|()n S n ⇔. 证毕.注 两个十进制正整数,其中一个被另一个正整数整除的条件，称为“整除的数字特征”.例5得出十进制正整数n 被9整除的数字特征是:“9整除n 的各位数字之和”.下面例题6得出十进制正整数n 被11整除的数字特征是:“11整除n 的各位数字的正负交错之和”.例6 设正整数n 的十进制表示为10(09,0)k i k n a a a a a =≤≤≠，n 的个位为起始数字的正负交错和 01()(1)k k T n a a a =-++-，证明：“11|n ”的充分必要条件是“11|()T n ”.证明 由于 101010k k n a a a =⨯++⨯+, 01()(1)k k T n a a a =-++-，1()(10(1))(10(1))(101)k k i i k i n T n a a a ∴-=--++--+++ 当i 为偶数时， 10(1)9999i i --= ，其中有偶数个9，显然它是11的倍数；当i 为奇数时，10(1)101(101)11()i i i s s s z --=+=+=∈， 它也是11的倍数,故总有11|(10(1)),(0).i i i k --≤≤ 即11|(())n T n -成立. 从而11|11|().n T n ⇔习题1.11．设n 是整数，则3|(1)(21)n n n ++. 2. 设正整数n 的十进制表示为10(09,0,0)k i k n a a a a i k a =≤≤≤≤≠，n 的个位为起始数字的正、负交错的和 01()(1)k k T n a a a =-++-，证明：“11|n ”的充分必要条件是“11|()T n ”.3. 若10个男孩和n 个女孩共买了282n n ++本书, 已知他们每人买的书本数量相同, 且女孩人数多于男孩人数, 问女孩人数是多少?4．证明一个整数a 若不能被2整除，也不能被3整除, 则223a +必能被24整除.5. 已知整数,,,m n p q 适合: (m - p ) ∣(mn + pq )，证明:(m - p )∣(mq + np ).对任意两个整数,(0)a b b ≠，a 未必能被b 整除. 为了能在整数范围内研究除法，引入整数的除法算法——带余数除法，它是初等数论证明中最重要、最基本、最常用的工具. 本节中，我们将介绍带余数除法及其简单应用. 我们约定, 以Z 表示所有整数的集合，N 表示所有正整数的集合. 除特别声明外，在涉及到带余数除法时总假定除数是正整数.1. 带余数除法定理1.2.1 (带余数除法) 设a 与b 是两个整数，b>0，则存在惟一的一对整数q 和r ，使得:a = bq + r ，0 ≤ r <b . (2)若a = bq + r (0 ≤ r < b ), 则|b a 的充分必要条件是0r =.证明: 存在性作整数序列: ,3,2,,0,,2,3,b b b b b b ---则a 必在上述序列的某两项之间,即存在一个整数q ,使得(1)qb a q b ≤<+成立. 令a qb r -=,则,a qb r =+而0.r b ≤<1.1.2 带余数除法惟一性 假设11,q r 是满足(2) 的两个整数，即 111(0),a bq r r b =+≤< 则 11a bq r bq r =+=+于是 1111()||||b q q r r b q q r r -=-⇒-=-(3)由上式推出: 1||b r r -,由于 110,0||r r b r r b <<⇒≤-<因此必有1||0r r -=,即1r r =，代入式(3)得 1q q =，惟一性得证.若a bq r =+(0)r b ≤<，则 ||,b a b r ⇔ 又 0r b ≤<, 则 |0.b r r ⇔=故|0.b a r ⇔= 证毕 注:这个结论揭示了整除与带余数除法之间的联系,说明了整除问题可以化归为带余数除法问题来解决.定义：在式a = bq + r （0 ≤ r < b ）中，q 称为a 被b 除的不完全商，r 称为a 被b 除的余数, 也称为最小非负剩余.带余数除法是一个重要的工具，数论的许多基本性质都是建立在带余数除法基础之上的.例1 当 15,225b a ==时有 1701022515,175,;r q <===⨯+ 当 15,417b a ==时有 1241715,15,;2072712q r <<===⨯+ 当 15,81b a ==-时, 有 0(6)8115,15,9;96q r --<=+<=-=⨯且有 (6)8115,(5)5;60,q r =--<=⨯-=--+ 此处{0,1,2,,151}r ∉-，这时的余数r 不是最小非负剩余。

初等数论初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++Λ2211 勾股数 费尔马大定理。

习题要求29p ：1，2，4；31p ：2，3。

第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。

习题要求60p ：1；64p ：1，2；69p ：1，2。

第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、素数模同余方程的解法习题要求78p ：2； 81p ：1，2，3；85p ：1，2；89p ：2；93p ：1。

第六章：原根与指标（2学时）自学8学时指数的定义及基本性质 原根存在的条件 指标及n 次乘余 模2 及合数模指标组、 特征函数习题要求123p ：3。

➢ 第一章 整除 一、主要内容筛法、[x]和{x}的性质、n ！的标准分解式。

二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。

认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。

信息安全数学基础答案【篇一：信息安全数学基础习题答案】xt>第一章整数的可除性1．证明：因为2|n 所以n=2k , k?z5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1 ，k1?z 7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1 即k1=7 k2，k2?z 所以n=2*5*7 k2 即n=70 k2, k2?z因此70|n32．证明：因为a-a=(a-1)a(a+1)3当a=3k，k?z 3|a 则3|a-a3当a=3k-1，k?z 3|a+1 则3|a-a3当a=3k+1，k?z 3|a-1 则3|a-a3所以a-a能被3整除。

3．证明：任意奇整数可表示为2 k0+1， k0?z22（2 k0+1）＝4 k0+4 k0+1=4 k0 (k0+1)+1由于k0与k0+1为两连续整数，必有一个为偶数，所以k0(k0+1)=2k2所以（2 k0+1）=8k+1 得证。

34．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a-a3由第二题结论3|（a-a）即3|(a-1)a(a+1)又三个连续整数中必有至少一个为偶数，则2|(a-1)a(a+1)又（3，2）=1所以6|(a-1)a(a+1) 得证。

5．证明：构造下列k个连续正整数列：(k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k?z对数列中任一数 (k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1],i=2,3,4,…(k+1) 所以i|(k+1)！+i即(k+1)！+i为合数所以此k个连续正整数都是合数。

1/26．证明：因为191＜14 ,小于14的素数有2，3，5，7，11，13经验算都不能整除191所以191为素数。

1/2因为547＜24 ,小于24的素数有2，3，5，7，11，13，17，19，23经验算都不能整除547所以547为素数。

第一章 整数的可除性§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 的因数。

信息安全数学基础第一阶段知识总结第一章整数的可除性一整除的概念和欧几里得除法1整除的概念定义1设a、b是两个整数，其中b丸如果存在一个整数q使得等式a=bq成立，就称b整除a或者a被b整除，记作b|a ,并把b叫作a 的因数，把a叫作b的倍数.这时，q也是a的因数，我们常常将q写成a/ b-或a否则，就称b不能整除a或者a不能被b整除，记作a b. 2整除的基本性质(1)当b遍历整数a的所有因数时，-b也遍历整数a的所有因数. ⑵当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数. ⑶设b, c都是非零整数，(i) 若b|a,则|b|||a|.(ii) 若b|a,贝卩bc|ac.(iii) 若b|a ,贝U 1<|b| <|a|.3整除的相关定理(1) 设a, b丸，c丸是三个整数若c|b, b|a,则c|a.⑵设a, b, c丸是三个整数，若c|a, c|b ,则c|a±b(3)设a, b , c是三个整数.若c|a, c|b则对任意整数s, t，有c|sa+tb.⑷若整数a i ,…,a都是整数c丸的倍数，则对任意n个整数%…，s n s整数—s n a n是c的倍数(5) 设a, b都是非零整数若a|b, b|a,贝S a= 士b(6) 设a, b , c是三个整数，且b #0, c丸,如果(a , c)=1,贝S (ab , c)=(b ,c)⑺设a , b , c是三个整数，且c丸，如果c | ab , (a , c) = 1,则c |b.(8) 设p是素数，若p |ab ,则p |a或p|b(9) 设a i ,…n是n个整数，p是素数，若p| a i…a ，则p 一定整除某一个a k二整数的表示主要掌握二进制、十进制、十六进制等的相互转化.三最大公因数和最小公倍数(一)最大公因数1. 最大公因数的概念定义：设I 厶是「二个整数，若丄」使得-I'.' ' 1-宀，则称丿为的一个因数.公因数中最大的一个称为心的最大公因数.记作-'.若仏角厂心)订则称卯角厂‘几互素.若@闷订(订血厂1,2,…町则称附昭两两互素.思考：1.由I J两两互素，能否导出_12. 由能否导出役两两互素？2 .最大公因数的存在性(1)若〕不全为零，则最大公因数-■■■■ -■■■存在并且（知…％）巩|乩…hh（2）若心全为零，则任何整数都是它的公因数.这时，它们没有最大公因数.3. 求两个正整数的最大公因数.定理1 :设心工〕任意三个不全为零的整数，且；丄则GO）讹©辗转相除法也』E N,由带余除法得旷如卄］0 < J沪也+与0〈勺〈勺if"4 % %】如胡因为每进行一次带余除法，余数至少减少1,且；是有限整数，故经过有限次带余除法后，总可以得到一个余数是零的情况，即7L °由（i）知，仏切=M= M=（训）=（s』定理2 :任意两个正整数「二则…丨-.\是（i）中最后一个不等于零的余数.定理3 :任意两个正整数；；1的任意公因数都是的因数.4 .性质定理4 :任意两个正整数S 则存在整数.:,使得二八—云成.立定理5 :设二门是不全为零的整数.⑴若J'贝ya _ (a,b)(ii) 若八财讨，则U 匚(iii) 若L是任意整数，贝S从上面定理我们很容易得到下面几个常用结论：①仏妨=1,方”②宓吗)J (订和J = 1,2厂说)且胡叨(尸1,2,…屈芋阳…务m③:④■—：'-■■■■■-5 .求两个以上正整数的最大公因数…;「：一一…一…:-则有下面的定理：定理6:若3是•个正整数，则1=4只需证①-、是/ ■■:的一个公因数.②J 是的公因数中最大一个例求-「二，二二解：八::m -.：-- ' '! .■■■：.：■- ：_]]：；,(58548.13776,10824,3567)-1236.求两个正整数的最大公因数的线性组合(重点掌握) 方法一运用辗转相除法求最大公因数的逆过程；方法二补充的方法方法三运用列表法求解(二)最小公倍数1 .最小公倍数的定义定义:[厶是—3个整数，如果对于整数匸，有讣("12…屈,那么朋叫做旳厂也的一个公倍数.在忙几的一切公倍数中最小一个正整数，叫做最小公倍数.记作+…—.2 .最小公倍数的性质.定理1 :设；是任给的两个正整数，则(i)仇占的所有公倍数都是肚对的倍数.仆)上d 广" ■■^^1定理2 :设正整数酬是必上的一个公倍数，贝^(ab) [ %]3.求两个以上整数的最小公倍数定理3 :设I厶是■个正整数，若' 则二f只需证：①S是【役的一个公倍数，即②设刖是附％的任一公倍数则叫吻例1求二解: (51X135)=27'[513J35] = 513X135=256527[513,135,3114] =[[513,135],3114] =[2565,3114] = 887490四素数算术基本定理1.素数、合数的概念定义：一个大于1的整数，如果它的正因数只有1和它的本身，我们 就称它为素数，否则就称为合数. 2 .性质定理1:设』是大于1的整数，贝債至少有一个素因数，并且当』是合 数时，若/是它大于1的最小正因数，贝, 定理2设n 是一个正整数，如果对所有地素数「n ,都有p n,则n —定是素数.求素数的基本方法：爱拉托斯散筛法。