(参考资料)初等数论：数的整除性

本讲中所涉及的数都是整数，所用的字母除特别申明外也都表示整数． ⑪整除设a 、b 是给定的数，0b ≠．若存在整数c ，使得a bc =，则称b 整除a ，记作b a ∣，并称b 是a 的一个约数（或因子），而称a 为b 的一个倍数．如果不存在上述的整数c ，则称b 不能整除a ，记作b a Œ．由整除的定义，容易推出整除的几个简单性质： ①若b ∣c ，且c a ∣，则b a ∣，即整除性质具有传递性． ②若b a ∣，且b c ∣，则()ba c ±∣，即某一个整数倍数的集合关于加法和减法运算封闭．反复应用这一性质，易知：若b a ∣及bc ∣，则对任意整数u 、v 有()b au cv +∣．更一般地，若1a ，2a ， ，n a 都是b 的倍数，则12()n ba a a ++ ∣． ③若b a ∣，则或者0a =，或者||a b ≥．因此，若b a ∣且a b ∣，则||||a b =．④（带余除法）对任意两个整数a 、b (0)b >，则存在整数q 和r ，使得a b q r =⋅+，其中0r b <≤，并且q 和r 由上述条件惟一确定．整数q 称为a 被b 除得的（不完全）商，数r 称为a 被b 除得的余数．r 共有b 种可能的取值，若0r =，即为前面说的a 被b 整除．易知，带余除法中的商实际上是a b ⎡⎤⎢⎥⎣⎦（不超过ab的最大整数），而带余除法的核心是关于余数的不等式：0r b <≤．⑤证明b a ∣的基本手法是将a 分解为b 与一个整数之积．在比较初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生．下面两个整除分解式在这类论证中应用较多． 若n 是正整数，则1221()()n n n n n n x y x y x x y xy y -----=-++++ ；若n 是正奇数，则1221()()n n n n n n x y x y x x y xy y ----+=+-+-+ ．⑫最大公约数与最小公倍数最大公约数是数论中的一个重要概念．设a 、b 不全为零，同时整除a 、b 的整数称为它们的公约数．因为a 、b 不全为零，故由整除的性质③推知，a 、b 的公约数只有有限多个，将其中最大的一个称为a 、b 的最大公约数，用符号()a b ，表示． 当()1a b =，时，即a ，b 的公约数只有1±，称a 与b 互素（或互质）．对于多于两个的不全为零的整数a ，b ， ，c ，可类似的定义它们的最大公约数()a b c ，，，．若()a b c ，，，1=，则称a ，b ， ，c 互素．但此时并不能推出a ，b ， ，c 两两互素；但反过来，若a ，b ， ，c 两两互素，则显然有()a b c ，，，1=． 由定义容易得到最大公约数的一些简单性质：任意改变a 、b 的符号和先后顺序不改变()a b ，的值，4整除即有()()()a b b a a b ±±==，，，；()a b ，作为b 的函数，以a 为周期，即()()a b a a b +=，，． 下面给出最大公约数的若干性质，它们是解决关于公约问题的基础．①设a 、b 是不全为0的整数，则存在整数x 、y ，使得()ax by a b +=，．如果00x x y y =⎧⎨=⎩是满足上式的一组整数，则00x x buy y au =+⎧⎨=-⎩（其中u 为任意整数）也是满足上式的整数．这表明，满足上式的x 、y 有无穷组，并且在0ab >时，可选择x 为正（负）数，此时y 则相应的为负（正）数．特别的，两个整数a 、b 互素的充分必要条件是存在整数x 、y ，使得1ax by +=，这通常称为a 、b 适合的裴蜀（Bezout ）等式．事实上，条件的必要性是性质①的特例．反过来，若有x 、y 使等式成立，设()a b d =，，则d a ∣且d b ∣，故d ax ∣及d by ∣，于是()d ax by +∣，即1d ∣，从而1d =． ②若m a ∣，m b ∣，则()m a b ，∣，即a 、b 任一个公约数都是它们的最大公约数的约数．③若0m >，则()()ma mb m a b =，，． ④若()a b d =，，则1a b d d ⎛⎫= ⎪⎝⎭，．因此，由两个不互素的整数，可自然地产生一对互素的整数． ⑤若()1a m =，，()1b m =，，则()1ab m =，．这表明，与一个固定整数互素的整数构成的集合关于乘法封闭．由此可以推出：若()1a b =，，则对任意0k >与()1k a b =，，进而对任意0l >有()1k l a b =，．⑥设bac ∣，若()1b c =，，则b a ∣． ⑦设正整数a 、b 之积是一个整数的k 次幂(2)k ≥．若()1a b =，，则a 、b 都是整数的k 次幂．一般地，设正整数a b c ，，，之积是一个整数的k 次幂，若a b c ，，，两两互素，则a b c ，，，都是整数的k 次幂．下面介绍最小公倍数．设a 、b 是两个非零整数，一个同时为a 、b 倍数的数称为它们的一个公倍数．a 、b 的公倍数有无穷多个，其中最小的正数称为a 、b 的最小公倍数，记作[]a b ，．对于多个非零整数a b c ，，，，可类似地定义它们的最小公倍数[]a b c ，，，． ⑧a 与b 的任意公倍数都是[]a b ，的倍数．对于多于两个整数的情形，类似的结论也成立． ⑨两个整数a 、b 的最大公约数与最小公倍数满足()[]||a b a b ab =，，． 思考：对于多于两个整数的情形，类似的结论不成立，请举出例子．⑩若a b c ，，，两两互素，则有[]||a b c ab c = ，，，．由此以及性质⑧可知若ad ∣，b d ∣， ，c d ∣，且a b c ，，，两两互素，则有ab c d ∣．⑬素数及唯一分解定理大于1的整数n 总有两个不同的正约数：1和n ．若n 仅有这两个正约数（称为n 没有真约数），则称n 为素数（或质数）．若n 有真约数，即n 可表示为a b ⋅的形式（这里a 、b 为大于1的整数），则称n 为合数．于是，正整数被分成三类，数1单独作一类，素数类及合数类．素数在正整数中特别重要，我们常用字母p 表示素数．由定义易得出下面的基本结论： ①大于1的整数必有素约数．②设p 是素数，n 是任意一个整数，则或者p 整除n ，或者p 与n 互素．事实上，p 与n 的最大公约数()p n ，必整除p ，故由素数的定义推知，或者()1p n =，，或者()p n p =，，即或者p 与n 互素，或者p n ∣．③设p 是素数，a 、b 为整数．若p ab ∣，则a 、b 中至少有一个数被p 整除．特别地可以推出，若素数p 整除(1)n a n ≥，则pa ∣． ④素数有无穷多个．思考：如何证明素数有无穷多个？（提示：用反证法，假设素数只有有限多个，为12k p p p ，，，，考虑数121k N p p p =+ ，利用性质⑬．①）⑤每个大于1的正整数都可以分解为有限个素数的积；并且，若不计素因数在乘积中的次序，这样的分解是唯一的．将n 的素因数分解中的相同的素因子收集在一起，可知每个大于1的正整数n 可惟一的表示为1212k a a a k n p p p = ，其中12k p p p ，，，是互不相同的素数，12k a a a ，，，是正整数，这称为n 的标准分解．⑥n 的全部正约数为1212k b b b k p p p ，其中i b 是满足0(12)i i b a i k = ，，，≤≤的任意整数． 由此易知，若记()n τ为n 的正约数的个数，()n σ为n 的正约数之和，则有12()(1)(1)(1)k n a a a τ=+++ ，121111212111()111k a a a k k p p p n p p p σ+++---=⋅---． 虽然素数有无穷多个，但它们在自然数中的分布却极不规则．给定一个大整数，判断它是否为素数，通常是极其困难的，要作出其标准分解，则更加困难．证明某些特殊形式的数不是素数（或者给出其为素数的必要条件），是初等数论中较为基本的问题，在数学竞赛中尤为常见．处理这类问题的基本方法是应用各种分解技术，指出所涉及数的一个真约数．【例 1】 证明：⑪设0m n >≥，有22(21)1)n m+-∣(2；⑫对正整数n ，记()S n 为n 的十进制表示中各个数位数码之和，则99()n S n ⇔∣∣． ⑬设p 和q 均为自然数，使得111112313181319p q =-+--+ ，证明：p 可被1979整除．【解析】 ⑪11112222221(21)[(2)21]mn n m n n ++-++-=-+++ 122(21)(21)n m+⇒--∣，又122221(21)(21)n nn+-=-+，从而122(21)(21)nn ++-∣． 于是由整除的传递性，有22(21)1)nm+-∣(2．⑫设101010k k n a a a =⨯++⨯+ ，其中09i a ≤≤，且0k a ≠，则01()k S n a a a =+++ ．于是有1()(101)(101)k k n S n a a -=-++- ．对1i k ≤≤，由整除分解式知9(101)i -∣，故上式右端k 个加项中的每一个都是9的倍数，从而由整除的性质知，它们的和也被9整除，即9(())n S n -∣．由此容易推出结论的两个方面． ⑶11111112231319241318p q ⎛⎫⎛⎫=++++-+++ ⎪ ⎪⎝⎭⎝⎭ 11111112313192659⎛⎫⎛⎫=++++-+++ ⎪ ⎪⎝⎭⎝⎭11111166013196611318989990⎛⎫⎛⎫⎛⎫=++++++ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭111197966013196611318989990⎛⎫=⨯+++ ⎪⨯⨯⨯⎝⎭【点评】 整除的性质②提供了证明12()n ba a a +++ ∣的一种基本的想法，我们可以试着去证明更强的（也往往是更容易证明的）命题：1i n ∀≤≤，有i ba ∣．这一更强的命题当然不一定成立，即使在它不成立的时候，上述想法仍有一种常常有效的变通：将12n a a a +++ 适当的分组成为12k c c c ++ ，而(12)i bc i k = ，，，∣． 例1⑫的证明，实际上给出了更强的结论，9())n n S n ∀-，∣(，即()(m od 9)S n n ≡．有些情形，我们能够由正整数十进制表示中的数字的性质，推断这个整数能否被另一个整数整除，这样的结论，常称为整除的数字特征．被2、3、5、10整除的数的数字特征是显而易见的．【变式】 设1k ≥是一个奇数，证明：(2)12)k k k n n n ∀++++ ，Œ(．【解析】1n =结论显然成立．设2n ≥，记所涉及的和为A ，则 22(2)(3(1))(2)k k k k k k A n n n =++++-+++ ．因为k 是正奇数，故由整除分解式可知，对每个2i ≥，数(2)k k i n i ++-被(2)2i n i n ++-=+整除，故2A 被2n +除得的余数是2，从而A 不可能被2n +整除（注意22n +>）．【点评】 论证中我们应用了“配对法”，这是数论中变形和式的一种常用手法．【变式】 设m 、n 为正整数，2m >，证明：(21)(21)m n -+Œ． 【解析】 当n m =时，结论平凡；当n m <时，结果可由1212121n m m -++<-≤推出来（注意2m >，并运用整除的性质③）； 当n m >的情形可化为上述特殊情形：由带余除法，n mq r =+，0r m <≤，而0q >．由于21(21)221n mq r r +=-++，由整除分解式知(21)(21)m mq --∣；而0r m <≤，故由上面证明了的结论知(21)(21)m r -+Œ（注意0r =时，结论平凡）．从而当n m >时也有(21)(21)m r -+Œ．这就证明了本题结论．【例 2】 设10a m n >>，，，证明：()(11)1m n m n a a a --=-，，． 【解析】 设(11)m n D a a =--，．通过证明()(1)m n a D -，∣及()(1)m n D a -，∣来推导出()1m n D a =-，，这是数论中证明两数相等的常用手法．∵()m n m ，∣，()m n n ，∣，由整除分解式即知()(1)(1)m n m a a --，∣，以及()(1)(1)m n n a a --，∣，故可知，()1m n a -，整除(11)m n a a --，，即()(1)m n a D -，∣． 为了证明()(1)m n D a -，∣，设()d m n =，． ∵0m n >，，∴可以选择0u v >，使得mu nv d -=．∵(1)m D a -∣，∴(1)mu D a -∣．同样，(1)nv D a -∣．故()mu nv D a a -∣，从而由mu nv d -=，得(1)nv d D a a -∣． 此外，因1a >，及(1)m D a -∣，故()1D a =，，进而()1nv D a =，．于是，从()mu nv D a a -∣可导出(1)d D a -∣，即()(1)m n D a -，∣． 综上所述，可知()1m n D a =-，．【变式】 记2210kk F k =+，≥．证明：若m n ≠，则()1m n F F =，． 【解析】 论证的关键是利用(2)n m F F -∣（例1⑪），即存在一个整数x 使得2m n F xF +=．不妨设m n >，()m n d F F =，，则由存在一个整数x 使得2m n F xF +=，推出2d ∣，所以1d =或2．但n F 显然是奇数，故必须1d =．【点评】(0)k F k ≥称为费马（Fermat ）数．本变式表明，费马数两两互素，这是费马数的一个有趣的基本性质．利用这一性质，可以证明素数有无穷多个的结论．无穷数列{}(0)k F k ≥中的项两两互素，所以每个k F 的素约数与这个数列中其他项的素约数不同，因此素数必然有无穷多个．【变式】 设0m n >，，22()mn m n +∣，则m n =． 【解析】 设()m n d =，，则11m m d n n d ==，，其中11()1m n =，．于是，条件转化为221111()m n m n +∣，故有22111()m m n +∣，从而211m n ∣．但11()1m n =，，故211()1m n =，．结合211m n ∣，可知必须11m =．同理11n =，因此m n =．【点评】 对两个给定的不全为零的整数，我们常借助它们的最大公约数，并应用性质⑵－④，产生两个互素的整数，以利用互素的性质作进一步论证（参见性质⑵－⑤，⑵－⑥．就本题而言，由于mn 为二次式，22m n +为二次齐次式，上述手段的实质是将问题化归成m 、n 互素这种特殊情形．在某些问题中，已知的条件（或者已经证明的结论）c a ∣并不使用，我们可以试着选取c 的一个恰当的约束b ，并从c a ∣过度到较弱的结论b a ∣，以期望后者提供适宜于进一步论证的信息．在本例中，我们就是由221111()m n m n +∣产生了211m n ∣，进而推导出11m =．【变式】 m 个盒子中各若干个球，每一次在其中)(m n n <个盒中加一球．求证：不论开始的分布情况如何，总可按上述方法进行有限次加球后使各盒中球数相等的充要条件是()1m n =，． 【解析】 设()1m n =，，则有u v ∈Z ，使得1(1)(1)un vm v m v =+=-++，此式说明：对盒子连续加球u 次，可使1m -个盒子各增加了v 个，一个增加(1)v +个．这样可将多增加了一个球的盒子选择为原来球数最少的那个，于是经过u 次加球之后，原来球数最多的盒子中的球与球数最少的盒子中的球数之差减少1，因此，经过有限次加球后，各盒球数差为0，达到各盒中的球数相等．用反证法证明必要性．若()1m n d =>，，则只要在m 个盒中放1+m 个球，则不管加球多少次，例如，加球k 次，则这时m 个盒中共有球kn m ++1（个），因为||1d m d n d >，，，所以kn m ++1不可能是d 的倍数，更不是m 的倍数，各盒中的球决不能一样多，因此，必须()1m n =，．【例 3】 设正整数a 、b 、c 的最大公约数为1，并且abc a b=-．证明：a b -是一个完全平方数．【解析】 方法一：设()a b d =，，则1a da =，1b db =，其中11()1a b =，．由于()1a b c =，，，故有()1d c =，． 于是问题中的等式转化为1111da b ca cb =-，由此可见11a cb ∣．因11(,)1a b =，故1a c ∣． 同样可得1b c ∣．再由11(,)1a b =便推出11a b c ∣（参考性质⑵－⑧⑨）．设11c a b k =，其中k 是一个正整数．一方面，显然k 整除c ；另一方面，结合1111da b ca cb =-， 得11()d k a b =-，故k d ∣．从而()k c d ，∣．但()1c d =，，故1k =． 因此11d a b =-．故211()a b d a b d -=-=．这就证明了a b -是一个完全平方数． 方法二：记a b k -=，则已知等式可化为2()k c b b -=．记()k b c d -=，． 若1d >，则d 有素因子p ．由上式知2p b ∣，故p ∣b ．结合()p b c -∣及p k ∣，得出p c ∣及p a ∣，这与()1a b c =，，相违． 因此1d =，进而知k 与c b -都是完全平方数．【变式】 设k 为正奇数，证明：(12)(12)k k k n n ++++++ ∣．【解析】 因为(1)122n n n ++++= ，故问题等价于证明：(1)n n +整除2(12)k k k n +++ ．因n 与1n +互素，所以这又等价于证明2(12)k k k n n +++ ∣．事实上，由于k 是奇数，故由整除的分解式，可知2(12)k k k n +++= [1(1)][2(2)][(1)1]2k k k k k k k n n n n +-++-++-++ 是n 的倍数．同理，2(12)[1][2(1)][1]k k k k k k k k k n n n n ++=+++-+++ 是1n +的倍数．【点评】 整除问题中，有时直接证明b a ∣不容易．若b 可分解为11b b b =，其中12()1b b =，，则我们可以将原命题b a ∣分解为等价的两个命题1b a ∣以及2b a ∣．本例应用了这一手法．更一般地，为了证明b a ∣，可将b 分解为若干两两互素的整数12n b b b ，，，之积，而证明等价的(12)i b a i n = ，，，∣（参见性质⑵－⑩）．【例 4】 设正整数a 、b 、c 、d 满足ab cd =，证明：a b c d +++不是素数． 【解析】 方法一：由ab cd =，可设a d m c b n ==，其中m 和n 是互素的正整数，由a m c n=意味着有理数ac 的分子、分母约去了某个正整数u 后，得到既约分数mn，因此a my =，c nu =．同理，有正整数使得b nv =，d mv =．因此，()()a bcd m n u v +++=++是大于1的整数之积，从而不是素数． 方法二：由ab cd =，得cd b a=．因此a b c d +++=cd a c d a +++()()a c a d a ++=．因为a b c d +++是整数，故()()a c a d a++也是整数，若它是一个素数，设为p ，则有()()a c a d ap ++=，可见p整除()()a c a d ++，从而p 整除a c +或a d +．不妨设()pa c +∣ ，则a c p +≥，结合⑶－③推出a d a +≤，矛盾．【变式】 设a 、b 是正整数，满足2223a a b b +=+，则a b -和221a b ++都是完全平方数． 【解析】 已知关系式即为2()(221)a b a b b -++=，论证的关键是证明正整数a b -与221a b ++互素．记(221)d a b a b =-++，．若d 有素因子p ，从而由性质⑶－①知2p b ∣．因p 是素数，故p b ∣．结合()p a b -∣知p a ∣．再由(221)p a b ++∣推导出p ∣1，矛盾，故1d =． 从而由性质⑶－①推知正整数a b -与221a b ++都是完全平方数．【例 5】 证明：两个连续正整数之积不能是完全平方，也不能是完全立方． 【解析】 反证法，假设有正整数x ，y 使得2(1)x x y +=．则24(1)4x x y +=22(21)41x y ⇔+=+(212)(212)1x y x y ⇔+++-=．因左边两个因数都是正整数，故有21212121x y x y ++=⎧⎨+-=⎩，解得0x y ==，矛盾．然而对于方程3(1)x x y +=，上面的分解方法不易奏效．采用另一种分解：设所说的方程有正整数解x 、y ，则由于x 和1x +互素，而它们的积是一个完全立方数，故x 与1x +都是正整数的立方，即3x u =，31x v +=，y uv =，u 、v 都是正整数，由此产生331v u -=，易知这不可能．不难看到，用类似的论证，可以证明连续两个正整数之积不会是整数的k 次幂（这里2k ≥）．【变式】 给定的正整数2k ≥，证明：连续三个正整数的积不能是整数的k 次幂． 【解析】 假设有正整数2x ≥及y ，使得(1)(1)k x x x y -+=．注意到上述式子左端的三个因数1x -、x 、1x +并非总两两互素，因此不能推出它们都是k 次方幂．克服这个困难的一种方法是将其变形为2(1)k x x y -=．因x 和21x -互素，故可由上式推出，有正整数a 、b ，使得k x a =，21k x b -=，ab y =，由此我们有221()k k k k a b a b =-=-22224221()()k k k k a b a a b a b b ----=-++++ ，由于2x ≥，故2a ≥，又2k ≥，故上式后一个因数必大于1，导出矛盾．【点评】 实际上，连续四个正整数的积也不能是整数的k 次幂，由于证明需要使用二项式定理，所以将在以后介绍．【例 6】 （09年集训队测试题）设n 是一个合数．证明存在正整数m ，满足|m n ，m n 3()()d n d m ≤．这里()d k 表示正整数k 的正约数的个数．【解析】 若n 有一个素因子p 满足p n ＞，令nm p=，则有m n ＜由p n ＞知()1m p =，，因此()()()2()d n d p d m d m ==．又由n 是合数知1m ＞，即()2d m ≥．因此2()()d n d m ≤．现在设n n 1m 为n n 2m 为1nm 的不n 21m ＞． 若不然，则1n m 没有大于1n 1n m 是合数，则它在区间1(1]n m ，内至少有一个因子，矛盾！因此1nm 是素数．但前面已假设n 的所有素因子都不大于n ，又1n n m n =1n n m =2m n 21m =矛盾！由21m ＞知121m m m ＞，且12m m 是n 的因子，由1m 的选取可知12m m n ＞，因此令312nm m m =，则有(123)i m n i =，，．因此，333123123123()()()()()max{()()()}d n d m m m d m d m d m d m d m d m =≤≤，，，故取123m m m ，，中因子数最多的一个为m 即可． 【点评】 以上用到一个基本的事实：若u v ，为正整数，则()()()d uv d u d v ≤，这可用数()d x 的计算公式推出来．【变式】 求出最小的正整数n ，使其恰有144个不同的正约数，且其中有10个连续约数．【解析】 从n 有10个连续正约数条件出发，我们不难得到n 必须被23410 ，，，，整除，对n 进行质因数分解进行讨论．n 是322357，，，的倍数，设n 的标准分解式为312235k r r r r k n p = ，则 12343211r r r r ，，，≥≥≥≥．又n 的正约数的个数12()(1)(1)(1)144k d n r r r =+++= ，而 1234(1)(1)(1)(1)432248r r r r ++++⨯⨯⨯=≥，因此 56(1)(1)(1)3k r r r +++ ≤．所以，在56k r r r ，，，中最多还有一个不为0． 要使n 最小，则5502k r =，≤≤．于是n 的形式为 35124235711r r r r r n =，此处12345321102r r r r r ，，，，≥≥≥≥≤≤．从而有1234(1)(1)(1)(1)144r r r r ++++=或12345(1)(1)(1)(1)(1)144r r r r r +++++=．显然当12345r r r r r ≥≥≥≥时，n 最小．由144222233=⨯⨯⨯⨯⨯，试算满足上式的数组12345()r r r r r ，，，，，得数组(52111)，，，，可使n 最小．这样，最小的52235711110880n =⨯⨯⨯⨯=．习题 1. 证明：⑪2001001 共能被1001整除； ⑫设正整数n 的十进制表示为10k n a a a = （090i k a a ≠，≤≤），记 01()(1)k k T n a a a =-++- （由n 个各位起始的数字的正、负交错和）． 证明：()n T n -被11整除．由此得出被11整除的数的数字特征：11整除n 的充分必要条件是11整除()T n ．【解析】 ⑪2001001 共201101=+367(10)1=+33663653(101)[(10)(10)101]=+-+-+ ，所以 1001∣2001001 0． ⑫()n T n -=0011()(10)[10(1)]k k k k a a a a a a -++++⨯-- ．按i 为偶数、奇数分别用整除分解式可以得到数10(1)i i i i a a ⨯--被11整除．因此()n T n -被11整除，故问题中结论的两方面均成立．习题 2. 利用Bezout 等式证明，任给整数n ，分数214143n n ++是既约分数．【解析】 ∵3(143)2(214)1n n +-+=，∴(214,143)n n ++1=．所以原命题成立．习题 3. 证明：对任意给定的正整数1n >，都存在连续n 个合数． 【解析】 容易验证，(1)!2,(1)!3,(1)!(1)n n n n +++++++ 是n 个连续的合数．习题 4. 求自然数N ，使它能被5和49整除，并且包括1和N 在内，它共有10个约数．【解析】 把N 写成素因数分解形式1223n a a a n N p = ，其中012i a i n = ，，，，≥． 则它所有约数的个数为12(1)(1)(1)10n a a a +++= ， 由于25|7|N N ，，则34121a a ++，≥≥3， 因此125n a a a a ，，，，必然都为0，即3457a a N =． 由于34(1)(1)1025a a ++==⨯，可得3414a a ==，， 即本题有唯一解457N =⋅．习题 5. 求所有的正整数对()a b ，，使得22(7)|()ab b a b a b ++++． 【解析】 由条件，22(7)|()ab b a b a b b ++++，而222()(7)7a b a b b a ab b b a ++=+++-，故22(7)|(7)ab b b a ++-．⑴当270b a ->时，要使22(7)|(7)ab b b a ++-，必须2277b a ab b -++≥，易知这不可能； ⑵当270b a -=时，即27b a =，此时a b ，应具有277*a k b k k ==∈N ，，的形式，经检验， 2()(77)a b k k =，，满足要求；⑶当270b a -<时，要使22(7)|(7)ab b b a ++-，必须2277a b ab b -++≥，那么2222777a b ab b ab b +++>⇒<≥，于是1b =或2b =．①1b =时，由题中条件2157788a a a a a ++=-+++是自然数，可知11a =或49a =，得解 ()(111)a b =，，或(491)，；②2b =时，由22(7)|(7)ab b b a ++-得7449a a -+是自然数，而74249a a -<+，所以74149a a -=+，此时133a =非自然数，舍去． 综上，所有解为2()(111)(491)(77)*a b k k k =∈N ，，，，，，，．建国60周年(四)我古老而年轻的祖国啊，我是你广袤大地上一棵稚嫩的幼苗，摇曳在你温暖呵护的怀抱，我是你无垠天空中一只飞翔的小鸟，鸣唱在你春风和煦的心头，我的血管里，涌动着黄河的波浪，我的心灵里，开放着文明的鲜花，我心中的理想，正展现在祖国蔚蓝的天空里。

初等数论（1）----数的整除初等数论又称初等整数论，它的研究对象是整数集。

整数是小学就接触的一类数，但是关于数论的问题却是最难解决的。

1、整数的离散性：任何两个整数,x y 之间的距离至少为1，因此有不等式1x y x y <⇔+≤。

例如：（1）若222912842440a ab b bc c c -+-+-+=，求a b c ++的值.（2）求整数,,a b c ，使它们满足不等式222332a b c ab b c +++<++.作比较。

2、整数的奇偶性：将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m （m ∈Z ），任一奇数可表为2m+1或2m －1的形式.关于奇数和偶数，有下面的性质：（1）奇数不会同时是偶数；两个连续整数中必是一个奇数一个偶数；（2）奇数个奇数和是奇数；偶数个奇数的和是偶数；任意多个偶数的和是偶数； （3）奇数±奇数=偶数；偶数±偶数=偶数； 奇数±偶数=奇数；偶数×偶数=偶数； 奇数×偶数=偶数；奇数×奇数=奇数；（4）两个整数的和与这两个整数的差有相同的奇偶性； （5）奇数的平方都可表为81m +形式，偶数的平方都可表为8m 或84m +的形式（m ∈Z ）. （6）任意两个整数的平方和被4除余数不可能是3. （7）任意两个整数的平方差被4除余数不可能是2.以上性质简单明了，解题时如果能巧妙应用，常常可以出奇制胜.例如： 1．（1）已知c b a ,,是整数，c b a ++是奇数，判断c b a -+，c b a +-，c b a ++-的奇偶性，说明理由。

（2）你能找到三个整数c b a ,,，使得关系式()()()()2010a b c a b c a b c b c a ++-++-+-=成立吗？如果能找到，请举一例，如果找不到，请说明理由.2、是否存在整数,m n ，满足222010m n +=?3、设1,2,3,,9的任一排列为1239,,,,a a a a ，求证：129(1)(2)(9)a a a ---是一个偶数. 类题：（1906，匈牙利）假设12,,,n a a a 是1,2,,n 的某种排列，证明：如果n 是奇数，则乘积()()()1212n a a a n ---是偶数.解法1 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，奇数个奇数的和还是奇数奇数=()()()1212n a a a n -+-++-()()12120n a a a n =+++-+++=，这与“奇数≠偶数”矛盾. 所以()()()1212n a a a n ---是偶数.评析 这个解法说明()()()1212n a a a n ---不为偶数是不行的，体现了整体处理的优点，但掩盖了“乘积”为偶数的原因. 解法2 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，i a 与i 的奇偶性相反，{}1,2,,n 中奇数与偶数一样多，n 为偶数但已知条件n 为奇数，矛盾. 所以()()()1212n a a a n ---是偶数.评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“n 为奇数”.那么为什么“n 为奇数”时“乘积”就为偶数呢？解法3 121,2,,,,,,n n a a a 中有1n +个奇数，放到n 个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得()()()1212n a a a n ---为偶数.例4-1（1986，英国）设127,,,a a a 是整数，127,,,b b b 是它们的一个排列，证明()()()112277a b a b a b ---是偶数.例4-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a 为该24个数字的任一排列，求证()()()12342324a a a a a a ---必为偶数.4、有n 个数12,,,n x x x ，它们中的每一个数或者为1，或者为1-，如果1234110n n n x x x x x x x x -++++=，求证：n 是4的倍数。

初等数论（4）（第一章数的整除性第四节最大公因数（1））定义1 整数a1，a2， ，a k的公共因数称为a1，a2， ，a k的公因数。

不全为零的整数a1，a2， ，a k的公因数中最大的一个叫做a1，a2， ，a k的最大公因数，记为（a1，a2， ，a k）。

由于每个非零整数的因数的个数是有限的，所以最大公因数是存在的，并且是正整数。

如果（a1，a2， ，a k）=1，则称a1，a2， ，a k是互质的；如果（a i , a j）=1，1 ≤i ≤k，1 ≤ j ≤k，i≠ j，则称a1，a2， ，a k是两两互质的。

显然，由a1，a2， ，a k两两互质可以推出（a1，a2， ，a k）= 1，反之则不然，例如（2，6，15）=1，但（2，6）= 2。

定理1 下面的等式成立：（ⅰ）（a1，a2， ，a k）=（|a1|，|a2|， ，|a k|）；（ⅱ）（a，1）=1，（a，0）=|a|，（a，a）=|a|；（ⅲ）（a，b）=（b，a）；（ⅳ）若p是质数，a是整数，则（p，a）=1或p∣a；（ⅴ）若a = bq + r，则（a，b）=（b，r）。

证明（ⅰ）我们先证明a1，a2， ，a k与|a1|，|a2|， ，|a k|的公因数相同。

设d是a1，a2， ，a k 任一公因数，由定义d∣ a i，i = 1，2，……，n。

因而d∣| a i | ，i = 1，2，……，n。

故d是|a1|，|a2|， ，|a k|的一个公因数,同样的方法可证|a1|，|a2|， ，|a k|的任一个公因数都是a1，a2， ，a k的一个公因数.即a1，a2， ，a k与|a1|，|a2|， ，|a k|的公因数相同。

由此可直接得（a1，a2， ，a k）=（|a1|，|a2|， ，|a k|）；（ⅱ）、（ⅲ）、（ⅳ）显然。

（ⅴ）如果d∣a，d∣b，则有d∣r = a -bq，反之，若d∣b，d∣r，则d∣a = bq + r。

数的整除知识点总结数的整除是数论中的一个基本概念，也是初等数学中的重要内容。

它与因数、倍数和约数等概念密切相关，对于解题和推理都有着重要的作用。

下面将对数的整除进行详细总结。

一、定义：如果整数a能够被整数b整除，即a/b是整数，那么称a是b的倍数，b是a的因数。

可以用数学表达式a=b*k来表示，其中k是整数。

二、性质：1.任何一个整数都是它自身的倍数，也是它自身的因数，即a是a的倍数，a是a的因数。

2.任何一个正整数都是1的倍数，即对于任何整数a，都有a是1的倍数。

3.任何一个整数都是它自身的因数，即对于任何整数a，都有a是a的因数。

4.如果a是b的倍数，b是c的倍数，那么a也是c的倍数，即若a是b的倍数且b是c的倍数，则a是c的倍数。

5.如果a是b的倍数，b是a的倍数，那么a和b是互为倍数，即a是b的倍数且b是a的倍数，则a和b互为倍数。

6.如果a是b的因数，b是c的因数，那么a也是c的因数，即若a是b的因数且b是c的因数，则a是c的因数。

三、判断一个数能否整除另一个数的方法：1.因式分解法：将被除数和除数都分解成质因数的乘积形式，然后进行比较。

如果被除数的质因数包含除数的质因数，并且对应质因数的指数均大于等于相应的质因数的指数，则被除数能够整除除数。

2.试商法：用除数去除被除数，如果商是整数且余数为0，则被除数能够整除除数，否则不能整除。

四、整除的性质：1.整除关系具有传递性，即如果a能够整除b，b能够整除c，则a 能够整除c。

2.整除关系具有反对称性，即如果a能够整除b，b能够整除a，则a 和b相等或互为相反数。

3.整除关系具有自反性，即任何一个数都能整除它本身。

4.整除关系具有非传递性，即如果a能够整除b，b能够整除c，但a 不能整除c。

例如：2能整除4，4能整除8，但2不能整除8五、整数的混合运算与整除的关系：1.若a整除b，b整除c，则a整除c。

2. 若a整除b，b整除c，则a整除bc。

初等数论讲稿几种常见数的整除特征初等数论是数论的一部分，主要研究自然数的性质和整数之间的关系。

在初等数论中，我们经常遇到一些特殊的数，它们具有特定的整除特征。

本文将介绍几种常见的数的整除特征。

首先，我们来讨论质数。

质数是只能被1和自身整除的自然数，比如2、3、5、7等。

质数的整除特征有两个：首先，任何自然数都可以被质数整除，这是因为质数本身没有其他的因数；其次，一个大于1的自然数若没有被小于等于它的任何一个质数整除，那就是质数，这就是质数的唯一性。

质数在密码学和随机数生成等领域有广泛的应用。

接下来，我们来讨论完全平方数。

完全平方数是可以写成一些自然数的平方形式的数，比如1、4、9、16等。

完全平方数的整除特征是，完全平方数的因数一定是成对出现的，即一个数的平方根之间的所有数都是它的因数。

例如，16的因数是1、2、4、8、16，可以看到它们是成对出现的。

然后，我们来讨论因子个数为奇数的数。

因子个数为奇数的数是指它的所有因数的个数是奇数的数。

例如，6的因数是1、2、3、6，共有4个，是偶数个；而9的因数是1、3、9，共有3个，是奇数个。

那么，什么样的数的因子个数为奇数呢？经过观察可以发现，只有完全平方数的因子个数为奇数。

因为对于一个完全平方数n，它的因数可以写成k的平方形式，其中k是小于等于n的自然数。

当n是完全平方数时，k的平方根只有一个，所以因子个数为奇数。

最后，我们来讨论约数和倍数。

一个数可以被另一个数整除，我们称之为约数。

而一个数可以整除另一个数，我们称之为倍数。

任何一个正整数都可以写成质数的乘积形式，所以对于给定的一个数，它的约数个数可以通过质因数分解的方式计算得到。

例如，对于数24，它的质因数分解是2^3*3^1，其中^表示幂。

那么它的约数个数可以计算为(3+1)(1+1)=8，其中3+1和1+1分别是2和3的幂次加1、而倍数则是一个数乘以任意整数得到的数，一个数的倍数个数是无穷大的。

例如，给定数3，它的倍数为3、6、9、12、15等。

第三篇 初等数论 第19章 整数的整除性§19．1整除19.1.1★证明：三个连续奇数的平方和加1，能被12整除，但不能被24整除． 解析 要证明一个数能被12整除但不能被24整除，只需证明此数等于12乘上一个奇数即可．设三个连续的奇数分别为21n -、21n +、23n +（其中n 是整数），于是()()()()22222121231121n n n n n -+++++=++．所以()()()22212|212123n n n ⎡⎤-++++⎣⎦．又()2111n n n n ++=++，而n 、1n +是相邻的两个整数，必定一奇一偶，所以()1n n +是偶数，从而21n n ++是奇数，故()()()22224212123n n n ⎡⎤-++++⎣⎦．19．1．2★★若x 、y 为整数，且23x y +，95x y +之一能被17整除，那么另一个也能被17整除． 解析 设23u x y =+，95x y =+．若17|u ，从上面两式中消去y ，得 3517v u x -=． ①所以17|3v ． 因为（17，3）=1，所以17|v 即17|95x y +．若17|v ，同样从①式可知17|5u ．因为（17，5）=1，所以17|u ，即17|23x y +． 19.1.3★★设n 是奇数，求证： 60|6321n n n ---．解析 因为260235=⨯⨯，22、3、5是两两互质的，所以只需证明22、3、5能整除6321n n n ---即可． 由于n 是奇数，有22|62n n -，22|31n +， 所以22|6231n n n ---； 又有3|63n n -，3|21n +， 所以3|6321n n n ---； 又有5|61n -，5|32n n +， 所以5|6321n n n ---．所以60|6321n n n ---． 评注 我们通常把整数分成奇数和偶数两类，即被2除余数为0的是偶数，余数为1的是奇数．偶数常用2k 表示，奇数常用21k +表示，其实这就是按模2分类．又如，一个整数a 被3除时，余数只能是0、1、2这三种可能，因此，全体整数可以分为3k 、31k +、32k +这三类形式，这是按模3分类．有时为了解题方便，还常把整数按模4、模5、模6、模8等分类，但这要具体问题具体处理．19．1．4★★设n 为任意奇正整数，证明：15961000270320n n n n +--能被整除． 解析 因为200621759=⨯⨯，所以为证结论成立，只需证n 为奇正整数时，15961000270320n n n n +--能被2、17、59整除．显然，表达式能被2整除． 应用公式，n 为奇数时，()()121n n n n n a b a b a a b b ---+=+-++， ()()121n n n n n a b a b a a b b ----=-+++.由于159610005944+=⨯，2703205910+=⨯，所以15961000270320n n n n +--能被59整除.又159627013261778-==⨯，10003206801740-==⨯，所以15961000270320n n n n +--能被17整除．19.1.5★★若整数a 不被2和3整除，求证：()224|1a -．解析 因为a 既不能被2整除，也不能被3整除，所以，按模2分类与按模3分类都是不合适的．较好的想法是按模6分类，把整数分成6k 、61k +、62k +、63k +、64k +、65k +这六类．由于6k 、62k +、64k +是2的倍数，63k +是3的倍数，所以a 只能具有61k +或65k +的形式，有时候为了方便起见，也常把65k +写成61k -（它们除以6余数均为5）． 故a 具有61k ±的形式，其中k 是整数，所以()()222161136121231a k k k k k -=±-=±=±．由于k 与31k ±为一奇一偶（若k 为奇数，则31k ±为偶数，若k 为偶数，则31k ±为奇数），所以()2|31k k ±，于是便有()224|1a -．19．1．6★★★求证：31n +（n 为正整数）能被2或22整除，但不能被2的更高次幂整除． 解析 按模2分类．若2n k =为偶数，k 为正整数，则 ()22313131n k n +=+=+．由3k 是奇数，()23k 是奇数的平方，奇数的平方除以8余1，故可设()2381k l =+，于是()3182241n l l +=+=+，41l +是奇数，不含有2的因数，所以31n +能被2整除，但不能被2的更高次幂整除． 若21n k =+为奇数，k 为非负整数，则()()()22131313313811461n k k l l ++=+=⋅+=++=+．由于61l +是奇数，所以此时31n +能被22整除，但不能被2的更高次幂整除． 19.1.7★★设p 是质数，证明：满足22a pb =的正整数a 、b 不存在. 解析 用反证法．假定存在正整数a 、b ，使得 22a pb =.令() , a b d =，1a a d =，1b b d =，则()11 , 1a b =.所以222211a d pb d =，2211a pb =，所以21|p a ．由于p 是质数，可知，1|p a .令12a pa =，则22221a p pb =，所以2221pa b =．同理可得，1|p b .即1a 、1b 都含有p 这个因子，这与()11 , 1a b =矛盾．19．1．8★★如果p 与2p +都是大于3的质数，那么6是1p +的约数.解析 每一整数可以写成6n 、61n -、61n +、62n -、62n +、63n +中的一种（n 为整数），其中6n 、62n -、62n +、63n +在1n ≥时都是合数，分别被6、2、2、3整除．因此，质数p 是61n -或61n +的形式. 如果()611p n n =+≥，那么()263321p n n +=+=+是3的倍数，而且大于3，所以2p +不是质数．与已知条件矛盾． 因此()611p n n =-≥．这时 16p n +=是6的倍数．评注 本题是将整数按照除以6，所得的余数分为6类． 质数一定是61n +或61n -的形式．当然，反过来，形如61n -或61n +的数并不都是质数．但可以证明形如61n -的质数有无穷多个，形如61n +的质数也有无穷多个．猜测有无穷多个正整数n ，使61n -与61n +同为质数．这是孪生质数猜测，至今尚未解决． 19.1.9★★已知a 、b 是整数，22a b +能被3整除，求证：a 和b 都能被3整除． 证 用反证法.如果a 、b 不都能被3整除，那么有如下两种情况：（1）a 、b 两数中恰有一个能被3整除，不妨设3|a ，3b ．令3a m =，31b n =±（m 、n 都是整数），于是()222222996133321a b m n n m n n +=+±+=+±+，不是3的倍数，矛盾．（2）a ，b 两数都不能被3整除.令31a m =±，31b n =±，则()()2222223131961961a b m n m m n n +=++±=±++±+()22333222m n m n =+±±+，不能被3整除，矛盾．由此可知，a 、b 都是3的倍数．19．1．10★★若正整数x 、y 使得2x x y+是素数，求证：x y ≤.解析 设2x p x y=+是素数，则()py x x p =-，所以()|p x x p -，故|p x ，或者|p x p -，故可得|p x ，且p x <.令x kp =，k 是大于1的整数，则()1y x k x =-≥．19.1.11★证明：形如abcabc 的六位数一定被7、11、13整除．解析100171113abcabc abc abc =⨯=⨯⨯⨯． 由此可见，abcabc 被7、11、13整除．19．1．12★任给一个正整数N ，把N 的各位数字按相反的顺序写出来，得到一个新的正整数N '，试证明：N N '-被9整除．解析N 除以9，与N 的数字和除以9，所得余数相同．N '除以9，与N '的数字和除以9，所得余数相同．N 与N '的数字完全相同，只是顺序相反，所以N 与N '的数字和相等．N 除以9与N '除以9，所得的余数相同，所以N N '-被9整除．19.1.13★19991999199919991999N =连写个.求N 被11除所得的余数．解 显然，N 的奇数位数字和与偶数位数字和的差为()1999999119998⨯+--=⨯.19998⨯除以11的余数与88⨯除以11的余数相同，即余数为9．从而N 除以11，所得的余数为9． 19．1．14★在568后面补上三个数字，组成一个六位数，使它能被3、4、5分别整除．符合这些条件的六位数中，最小的一个是多少？ 解析 要命名这个六位数尽可能小，而且能被5整除，百位数字和个位数字都应选0．这样，已知的五个数位上数字之和是5+6+8+0+0=19．要使这个六位数能被3整除，十位上可填2、5、8．由能被4整除的数的特征（这个数的末两位数应该能被4整除）可知，应在十位上填2．这个六位数是568020．19.1.15★★已知四位数abcd 是11的倍数，且有b c a +=，bc 为完全平方数，求此四位数． 解析在三个已知条件中，b c a +=说明给出b 和c ，a 就随之给定，再由11|abcd ，可定d .而bc 为完全平方数，将b 和c 的取值定在两位平方数的十位和个位数字范围中，只要从这个范围中挑选符合要求的即可．由bc 完全平方数，只可能为16、25、36、49、64、81这六种情况．由b c a +=，此时相应的a 为7、7、9、13、10、9．其中13和10显然不可能是四位数的千位数字．在716d 、725d 、936d 、981d ，这四种可能性中，由11|abcd ，应有()()11|d b a c +-+．()()11|176d +-+时，d 可为1； ()()11|275d +-+时，这种d 不存在； ()11|396d +-+时，d 可为1；()11|891d +-+时，d 可为2．故满足条件的四位数有：7161、9361、9812．评注bc 为完全平方数，表示bc 是两位整数，0b ≠，因此，不考虑00、01、04、09这四种情况，否则还应加上1012、4048、9097这三个四位数.19．1．16★★用0，1，2，…，9这十个数字组成能被11整除的最大的十位数是多少？ 解析 因为0+1+2+…+9=45．这个最大十位数若能被11整除，其奇数位上数字之和与偶数位上的数字之和的差（大减小）为0或11的倍数．由于这十个数字之和是45（奇数），所以这个差不可能是0、22、44（偶数）．若这个差为33，则只能是396-，但0+1+2+3+4=10，即最小的五个数字之和都超过6，不可能．若这个差为11，()4511228+÷=，452817-=．如果偶数位为9、7、5、3、1，其和为25；奇数位为8、6、4、2、0，其和为20．交换偶数位上的1与奇数位上的4，可得偶数位上的数为9、7、5、4、3，奇数位上的数为8、6、2、1、0．19.1.17★★一个六位数88的倍数，这个数除以88所得的商是多少？ 解析 设这个六位数为1234A B ，因为它是88的倍数，而88811=⨯，8与11互质，所以，这个六位数既是8的倍数，又是11的倍数．由1234A B 能被8整除，可知34B 能被8整除（一个数末三位组成的数能被8整除，这个数就能被8整除），所以B 是4．由能被11整除的数的特征（一个数奇数位数字之和与偶数位数字之和的差能被11整除，这个数就能被11整除），可知奇数位数字之和与偶数位数字之和的差()()234144A A ++-++=-能被11整除，则40A -=，即4A =． 124344881413÷=．所以，这个六位数是124344的商是1413．19．1．18★★如果六位数105整除，那么，它的最后两位数是多少？ 解析 因为这个六位数能被105357=⨯⨯，3、5、7这三个数两两互质，所以，这个六位数能同时被3、5、7整除．根据能被5整除的数的特征，它的个位数可以是0或5．根据能被3整除的数的特征，可知这个六位数有如下七种可能：199320，199350，199380，199305，199335，199365，199395．而能被7整除的数的特征是：这个数的末三位数字所表示的数与末三位以前的数字所表示的数的差（以大减小）能被7整除．经试算：395199196-=，196能被7整除．所以，199395能被105整除，它的最后两位数是95．19.1.19★★形如1993199319931993520n 个，且能被11整除的最小数是几？解析 本题实质上确定n 的最小值．利用被11整除的数的特征：偶数位数字之和与奇位数字之和的差能被11整除．该数的偶数位数字之和为122n +，奇数位数字之和为105n +，两者之差为()12210523n n n +-+=-．要使()11|23n -，不难看出最小的7n =，故所求最小数为71993199319931993520个．19．1．20★★★是否存在100个不同的正整数，使得它们的和与它们的最小公倍数相等？ 解析 存在满足条件的100个数．事实上，对任意正整数()3n ≥，下述n 个数3，23⨯，223⨯，…，223n -⨯，13n -， 它们的最小公倍数为123n -⨯，和为221222132323233323233n n n n ----+⨯+⨯++⨯+=+⨯++⨯+33211113232333323n n n n n -----=+⨯++⨯+==+=⨯．所以，这几个数的和等于它们的最小公倍数．取100n =，可知存在符合要求的100个数．19.1.21★★下面这个41位数20555个 2099个能被7整除，问中间方格代表的数字是几？解析 因为5555555111111=⨯，9999999111111=⨯，11111137111337=⨯⨯⨯⨯，所以555555和999999都能被7整除，那么由18个5和18个9分别组成的18位数，也能被7整除．而原数=185230555000个个1851890999+个个，因此右边的三个加数中，前后两个数都能被1整除，那么只要中间的能被7整除，7整除．把拆成两个数的和： 5599BA B +.因为7|55300，7|399336+=． 评注 记住111111能被7整除很有用．19．1．22★★一位魔术师让观众写下一个六位数a ，并将a 的各位数字相加得b ，他让观众说出a b -中的5个数字，观众报出1、3、5、7、9，魔术师便说出余下的那个数，问那个数是多少？ 解析 由于一个数除以9所得的余数与这个数的数字和除以9所得的余数相同，所以a b -是9的倍数．设余下的那个数为x ，则 ()9|13579x +++++， 即()9|7x +，由于09x ≤≤，所以，2x =．19．1．23★★若p 、q 、21p q -、21q p-都是整数，并且1p >，1q >．求pq 的值．解析 若p q =，则 212112p p q p p--==- 不是整数，所以p q ≠．不妨设p q <，于是2121212p q q q q q --<<=≤，而21p q -是整数，故211p q -=，即21q p =-．又 214334q p p p p--==- 是整数，所以p 只能为3，从而5q =．所以 3515pq =⨯=．19．1．24★★★试求出两两互质的不同的三个正整数x 、y 、z 使得其中任意两个的和能被第三个数整除． 解析 题中有三个未知数，我们设法得到一些方程，然后从中解出这些未知数．不妨设x y z <<，于是y z x +、z x y +、x yz+都是正整数．先考虑最小的一个：12x y z z z z++<=≤，所以1x yz+=，即z x y =+．再考虑z x y +，因为()|y z x +，即()|2y y x +，所以|2y x ，于是2212x y y y <=≤， 所以21xy=，即2y x =，从而这三个数为x 、2x 、3x ．又因为这三个数两两互质，所以1x =． 所求的三个数为1、2、3．19.1.25★★★求所有的有理数a ，使得421a -≤，并且44127a A a -=为整数.解析 由条件，可知1344a ≤≤.当14时，0A =是整数；下面考虑1344a <≤的情形，此时设pa q =，p 、q 为正整数，且() , 1p q =．则由()34427p q p A q -=为正整数和() , 1p q =可知4|4q q p -，进而|4q q p -，导致|q p ，再结合() , 1p q =，得1q =. 于是()3427p p A -=，又114a p =>．故3p ≤，易知仅当3p =时A 为正整数． 综上可知，满足条件的14a =或13． 19．1．26★★设正整数x 、y 、r 、t 满足1100x y r t <<<≤≤．求x ry t+的最小值． 解析 由条件，可知11111121100100100100100100x r r y y y t y y y ++++=++=≥≥≥. 等号在()() , , , 1 , 10 , 11 , 100x y r t =时取到，因此所求的最小值为21100. 19.1.27★★已知正整数a 、b 、p 、q 、r 、s 满足条件1qr ps -=，p a rq b s<<．证明：b q s +≥． 解析 由条件，可知pb aq <，as br <，故 1pb aq +≤， ① 1as br +≤． ②将①s ⨯与②q ⨯，然后相加，得 psb s q brq ++≤．结合1rq ps -=，可知b q s +≥.19．1．28★★★将正整数N 接写在任意一个正整数的右面（例如，将2接写在35的右面得352），如果得到的新数都能被N 整除，那么N 称为“魔术数”.问：在小于130的正整数中有多少个魔术数？ 解析 设P 为任意一个正整数，将魔术数()130N N <接后得PN ，下面对N 为一位数、两位数、三位数分别进行讨论．（1）当N 为一位数时，10PN P N =+，依题意|N PN ，则|10N P .由于需对任意数P 成立，故|10N ．所以N =1，2，5．（2）当N 为两位数时，100PN P N =+，依题意|N PN ，则|100N P ，故|100N ．所以N =10，20，25，50．（3）当N 为三位数时，1000PN P N =+，依题意|N PN ，则|1000N P ，故|1000N ．所以100N =，125．综上所述，魔术数的个数为9个． 评注 （1）我们可以证明：k 位魔术数一定是10k 的约数．事实上，设N 是k 位魔术数，将N 接写在正整数P 的右面得：10k PN P N =⨯+，由魔术数定义可知：|N PN ，因而10k P ⨯也能被N 整除，所以|10k N ．这样我们有：一位魔术数为1，2，5；二位魔术数为10，20，25，50；三位魔术数为100，125，200，250，500； 三位或三位以上的魔术数，每种个数均为5．（2）这里将问题分成几种情况去讨论，对每一种情况都增加了一个前提条件，从而降低了问题的难度，使问题较容易解决．19.1.29★★一个正整数如果从左读到右与从右到左读所得的结果相同，则称这个数为回文数．例如：1，343及都是回文数，但则不是．请问能否找到个不同的回文数122005 , , , n n n ，使得122005110 , 110 , , 110n n n +++也都是回文数？解析 取回文数10999901n =，则11011000011n +=也是回文数．因为n 中9的数目可以任选，可取110901n =，2109901n =，…，20052005910999901n =个，因此我们可以找到个回文数满足题目所要求的条件．19．1．30★★将个同学排成一行，并从左向右编为1至号．再从左向右从1到11地报数，报到11的同学原地不动，其余同学出列．留下的同学再次从左向右从1到11地报数，报到11的同学留下，其余同学出列．留下的同学第三次从左向右1到11报数，报到11的同学留下，其余同学出列．问最后留下的同学有多少人？他们的编号是几号？ 解 由题意，第一次报数后留下的同学，他们的编号必为11的倍数． 第二次报数后留下的同学，他们的编号必为211121=的倍数． 第三次报数后留下的同学，他们的编号必为3111331=的倍数．因此，最后留下的同学编号为1331的倍数，我们知道从1~中，1331的倍数只有一个，即1331号．所以，最后留下一位同学，编号为1331．19.1.31★★★甲、乙两人进行了下面的游戏．两人先约定一个整数N ，然后由甲开始，轮流把0、1、2、3、4、5、6、7、8、9这十个数字之一填入下面的任一方格中．□□□□□□每一方格只填一个数字，六个方格都填上数字（数字可重复）后，就形成一个六位数，如果这个六位数能被N 整除，就算乙胜；如果这六位数不能被N 整除，就算甲胜．设N 小于15，那么当N 取哪几个数时，乙才能取胜？解析N 取偶数，甲可以在最右边方格里填一个奇数（六位数的个位），就使六位数不能被N 整除，乙不能获胜．5N =，甲可以在六位数的个位填一个不是0或5的数，甲就获胜．上面已经列出了乙不能获胜的N 的取值情况． 如果1N =，很明显乙必获胜．如果3N =或9，那么乙在填最后一个数时，总是能把六个数字之和凑成3的整数倍或9的整数倍．因此乙必获胜． 当7N =，11，13时是本题最困难的情况．注意到100171113=⨯⨯，乙就有一种必胜的办法．我们从左往右数这六个格子，把第一与第四，第二与第五，第三与第六配对，甲在一对格子的一格上填某一个数字后，乙就在这一对格子的另一格子上填同样的数字，这就保证所填成的六位数能被1001整除，这个六位数就能被7、11或13整除，故乙就能获胜． 综合起来，使乙获胜的N 是1、3、7、9、11、13．19．1．32★★小明家电话号码原为六位数，第一次升位是在首位号码和第二位号码之间加上数字8，成为一个七位数的电话号码；第二次升位是在首位号码前加上数字2，成为一个八位数的电话号码．小明发现，他家两次升位后的电话号码的八位数，恰是原来电话号码的六位数的81倍，问小明家原来的电话号码是多少？ 解析设原来电话号码的六位数为abcdef ，则经过两次升位后电话号码的八位数为28a bcdef ．根据题意，有 8128abcdef a bcdef ⨯=．记43210101010x b c d e f =⨯+⨯+⨯+⨯+， 于是5568110812081010a x a x ⨯⨯+=⨯+⨯+，解得 ()125020871x a =⨯-． 因为5010x <≤，所以()5012502087110a ⨯-<≤， 故1282087171a <≤. 因为a 为整数，所以2a =．于是 ()125020871282500x =⨯-⨯=．所以，小明家原来的电话号码为282500． 19.1.33★★若a 是不超过1000的正整数，且247a a ++是最简分数，则a 的取值有多少个？ 解析 因为2723444a a a a +=-+++，所以()4 , 231a +=，由于23是质数，所以4a +不是23的倍数即可，在5，6，…，1004中，23的倍数有43个，所以满足条件的正整数a 有100043957-=个．19．1．34★★★★在各位数码各不相同的10位数中，是11111的倍数的数共有多少个．解析 设这个10位数为abcdefghij ，因为这10位数的各位数码各不相同，所以a 、b 、c 、d 、e 、f 、g 、h 、i 、j 是0 , 1 , 2 , , 9的一个排列，故 45a b c d e f g h i j +++++++++=．所以9|abcdefghij ．因为11111|abcdefghij 且（11111，9）=1，所以99999|abcdefghij ，即599999|10abcde fghij ⨯+．又99999|99999abcde ⋅，所以99999|abcde fghij +．因为0999992abcde fghij <+<⨯，所以99999abcde fghij +=， 所以9a f b g c h d i e j +=+=+=+=+=．而99081726354=+=+=+=+=+，所以，符合题意的数共有 54543212432123456⨯⨯⨯⨯⨯-⨯⨯⨯⨯=（个）．19.1.35★★★从1，2，…，9这九个数字中，每次取出3个不同的数字组成三位数，求其中能被3整除的三位数的和． 解析 对于固定的三个不同的非零数字a 、b 、c ，任意排列，可得6个不同的三位数，它们的和为()2111a b c ++⨯．因为()3|3|abc a b c ⇔++，所以有以下两种情况：（1）a 、b 、c 除以3所得的余数相同，即a 、b 、c 取成{}1 , 4 , 7，或{}2 , 5 , 8，或{}3 , 6 , 9，这样得到的()332118⨯⨯⨯=个的三位数的总和为 ()()()21472583691119990++++++++⨯=⎡⎤⎣⎦． （2）a 、b 、c 除以3所得的余数各不相同，不妨设a 取自{}1 , 4 , 7，b 取自{}2 , 5 , 8，c 取自{}3 , 6 , 9，这种三位数共有()333321162⨯⨯⨯⨯⨯=个．对于固定的a ，易知b 、c有339⨯=种取法，因而这162个三位数的和为 ()91239211189910++++⨯⨯=．综合（1）、（2），可知，所求的满足条件的三位数总和为 9990+89910=99900．19．1．36★★★证明一个正整数，当且仅当它不是2的整数幂时，可以表示成若干个（至少两个）连续正整数的和． 解析 当且仅当，有两方面的意思．一方面，当一个正整数不是2的整数幂时，它可以表示成几个连续正整数的和．另一方面，如果一个正整数可以表示成几个连续正整数的和，那么它一定不是2的整数幂．设n 不是2的整数幂．这时n 可以写成 2k n h =⋅，h 是大于1的奇数. ①我们可将n 写成h 个连续正整数的和．中间一个是2k ，它的两侧是21k -与21k +，再向外分别写22k -与22k +，…，直至122k h --与122k h -+（h 是奇数，所以12h -是整数），即()()132********k k k k kh h n --⎛⎫⎛⎫=-+-++-+++++ ⎪ ⎪⎝⎭⎝⎭312222k k h h --⎛⎫⎛⎫+++ ⎪ ⎪⎝⎭⎝⎭．另一方面，设n 是()1h h >个连续正整数1k +，2k +，…，k h +的和，则()()()()()11122122k k h hn k k k h k h h +++=++++++==++，其中h 与21k h ++奇偶性不同，即至少有一个是大于1的奇数．所以这时n 不是2的整数幂． 评注 2的整数幂没有大于1的奇约数．所以一个整数，如果有大于1的奇约数就一定不是2的整数幂．19.1.37★★★玛丽发现将某个三位数自乘后，所得乘积的末三位数与原三位数相同．请问：满足上述性质的所有不同的三位数的和是多少？ 解析设三位数为abc ，则21000abc k abc =+， 即()33125abc abc k -=⋅，而(), 11abc abc -=，所以，32|abc ，且35|1abc -；或者32|1abc -，且35|abc ． （1）若32|abc ，且35|1abc -，则1125abc -=，375，625，875，只有376abc =使得32|abc ，故此时376abc =满足题意．（2）若32|1abc -，且35|abc ，则125abc =，375，625，875，只有625abc =使得32|1abc -，故此时625abc =满足题意．所以，所求的和为376+625=1001．19．1．38★★★我们知道，4998约分后是12，但按下面的方法，居然也得14941:29882==.试求出所有分子和分母都是十进制两位正整数，分子的个位数与分母的十位数相同，且具有上述“奇怪”性质的真分数．解析 设真分数ab bc 具有上述性质，则ab bc <，且1ab acbc =<，于是 1010a b ab c c+=+，故()910ac b a c =-．若()9|10a c -，则()9|a c -，但是9a c -<，所以0a c -=，矛盾．故9不整除10a c -，所以3|b ．（1）若3b =，则310ac a c =-，于是10333131a a c a a -==+++，所以()()31|3a a +-，而331a a -<+，故只能是3a =，从而3c =，矛盾．（2）若6b =，则()3210ac a c =-，于是2021263232a a c a a -==+++，当6a >时，021232a a <-<+，此时c 不是整数；当6a =时，6c =，矛盾；当6a <时，应有12232a a -+≥，所以2a ≤，而当1a =时，4c =，此时，满足题意的真分数为1664，当2a =时，5c =，此时，满足题意的真分数为2665．（3）若9b =，则10ac a c =-，于是10101011a c a a ==-++，所以，()1|10a +，故a =1，4，9． 当1a =时，5c =，此时，满足题意的真分数为1995；当4a =时，8c =，此时，满足题意的真分数为4998；当9a =时，9c =，矛盾．综上所述，满足题意的真分数为：1664，2665，1995，4998. 19.1.39★★★在1，2，3，…，1995这1995个数中，找出所有满足下面条件的数a ：()1995a +能整除1995a ⨯．解析 19951995aa+是一个整数．这个式子的分子、分母都有a ，所以应当先进行变形，使得分子不含有a ．()19951995199519951995199519951995199519951995a a a a a+-⨯⨯==-+++.根据已知，19951995a a +是整数，所以199519951995a⨯+是整数．因为22221995199535719⨯=⨯⨯⨯，所以它的因数1995a +可以通过检验的方法定出．注意11995a ≤≤，所以199519953990a <+≤．如果1995a +不被19整除，那么它的值只能是以下两种： 223573675⨯⨯=，223572205⨯⨯=．如果1995a +被19整除，而不被219整除，那么它的值只能是以下两种： 237192793⨯⨯=，257193325⨯⨯=．如果1995a +被219整除，那么它的值只能是以下两种： 27192527⨯=，223193249⨯=．于是满足条件的a 有6个，即从以上1995a +的6个值分别减去1995，得出的6个值： 1680，210，798，1330，532，1254．评注 形如ac a b +的式子，可以化成cbc a b-+.使得只有分母含a ，而分子不含a ．这种方法有点像假分数化成带分数．19．1．40★★★在1，2，…，这个正整数中，最多可以取出多少个数，使得所取出的数中任意三个数之和都能被33整除？ 解析 首先，如下61个数：11，11+33，11233+⨯，…，()1160331991+⨯=满足题设条件．另一方面，设12n a a a <<<是从1，2，…，中取出的满足题设条件的数，对于这n 个数中的任意4个数 , , , i j k m a a a a ，因为()33|i k m a a a ++，()33|j k m a a a ++，所以()33|j i a a -． 因此，所取的数中任意两个之差都是33的倍数．设133i i a a d =+， 2 , 3 , , i n =.由()12333|a a a ++，得()12333|33333a d d ++． 所以133|3a ，111|a ，即111a ≥．1201011613333n n a a d --=<≤，故60n d ≤，所以，61n ≤． 综上所述，n 的最大值为61．19.1.41★★★圆周上放有N 枚棋子，如图所示．B 点的棋子紧邻A 点的棋子．小洪首先拿走B 点的棋子，然后顺时针每隔1枚拿走2枚棋子．这样连续转了10周．9次越过A ，当将要第10次越过A 取走其他棋子时，小洪发现圆周上余下20多枚棋子．若N 是14的倍数，请帮助小洪精确计算一下圆周上还有多少枚棋子． 解析 如果在A 、B 之间再添一枚棋子，并在第一次取棋子时将它取走，那么每一次都是在相邻3枚棋子中取走2枚，所以每取一周，剩下的棋子是上一次剩下的13．设最后剩下a 枚棋子．根据分析所说 1013N a +=， ① 即1031N a =⨯-．因为N 是14的倍数，所以N 是偶数，a 是奇数．又N 是7的倍数，而10539==（7的倍数）+52=（7的倍数）+4，所以41a -是7的倍数．因为a 是20与29之间的奇数，将a =21，23，25，27，29代入41a -，逐一检验，只有a =23时，4191713a -==⨯是7的倍数． 所以圆周上还有23枚棋子． 评注 在A 、B 之间添上一枚棋子，使得取棋子有明显的规律，从而得到①．这是一种很巧妙的想法．在计算103除以7的余数时，可以将其中7的倍数抛弃，直至出现小于7的4．这是常用的方法．19．1．42★★★★求证：对1i =，2，3，均有无穷多个正整数n ，使得n ，2n +，28n +中恰有i 个可表示为三个正整数的立方和． 解析 三个整数的立方和被9除的余数不能为4或5，这是因为整数可写为3k 或31k ±（k是整数），而()33393k k =⨯，()()332319331k k k k ±=±+±．对1i =，令()33312n m =--（m 是正整数），则n 、28n +被9除的余数分别为4、5，故均不能表示为三个整数的立方和，而()()()3332313131n m m m +=-+-+-．对2i =，令()331222n m =-+（m 是正整数）被9除的余数为5，故不能表示为三个整数的立方和，而()3323126n m +=-++， ()333283155n m +=-++．对3i =，令3216n m =（m 是正整数）满足条件： ()()()333345m m m m =++， ()3332611n m +=++，()33328613n m +=++．§19．2奇数与偶数19.2.1★设有101个自然数，记为12101 , , , a a a ．已知12310123101a a a a s ++++=是偶数，求证：13599101a a a a a +++++是偶数． 解析 ()1359910123451001012244100100a a a a a s a a a a a a +++++=-++++++是偶数．19．2．2★设121998 , , , x x x 都是1+或者1-．求证：12319982319980x x x x ++++≠．解析()12319981351997231998351997x x x x x x x x ++++=++++()241998241998x x x ++++.因为131997 , 3 ,, 1997x x x 这999个数均为奇数，所以它们的和为奇数，于是B12199821998x x x +++=奇数0≠．19.2.3★★设()12 , , , 4n x x x n >为1+或为1-，并且123423451230n x x x x x x x x x x x x +++=．求证：n 是4的倍数． 解析 设12342345123 , , , n x x x x x x x x x x x x 中1+有k 个，于是1-也有k 个，故2n k =为偶数．把12342345123 , , , n x x x x x x x x x x x x 这n 个数相乘，得()()4121kn x x x =-，所以()11k-=．故k 是偶数，从而n 是4的倍数．19．2．4★某次数学竞赛，共有40道选择题，规定答对一题得5分，不答得1分，答错倒扣1分．证明：不论有多少人参赛，全体学生的得分总和一定是偶数． 解析 我们证明每一个学生的得分都是偶数．设某个学生答对了a 道题，答错了b 道题，那么还有40a b --道题没有答．于是此人的得分是()5404240a a b b a b +---=-+，这是一个偶数．所以，不论有多少人参赛，全体学生的得分总和一定是偶数． 19.2.5★把前50个正整数分成两组，使第一组内各数之和等于第二组内各数之和，能办到吗？说明你的理由． 解析 不能办到．如果能办到，那么所有数加起来应该是第一组内各数之和的2倍，是偶数，但这50个数的总和为5051125025512⨯+++==⨯是个奇数，矛盾！19．2．6★设1，2，3，…，9的任一排列为129 , , , a a a ，求证：()()()129129a a a ---是一个偶数．解析 因为()()()()()()123912912391290a a a a a a a -+-+-++-=+++-+++=是偶数，所以，()()()1291 , 2 ,, 9a a a ---这9个数中必定有一个是偶数，从而可知()()()129129a a a ---是偶数．解析2 由于1，2，…，9中只有4个偶数，所以1a 、3a 、5a 、7a 、9a 中至少有一个是奇数，于是11a -、33a -、55a -、77a -、99a -中至少有一个是偶数，从而()()()129129a a a ---是偶数.19.2.7★有n 个数12 , , , n x x x ，它们中的每一个数或者为1，或者为1-，如果1223110n n n x x x x x x x x -++++=，求证：n 是4的倍数． 解析 我们先证明2n k =为偶数，再证k 也是偶数．由于12 , , , n x x x 的绝对值都是1，所以12231 , , , n x x x x x x 的绝对值也都是1，即它们或者是为1+，或者为1-，设其中有k 个1-，由于总和为0，故1+也有k 个，从而2n k =． 下面我们来考虑()()()12231n x x x x x x ⋅⋅⋅.一方面，有()()()()122311kn x x x x x x ⋅⋅⋅=-，另一方面，有()()()()212231121n n x x x x x x x x x ⋅⋅⋅==．所以()11k-=，故k 是偶数，从而n 是4的倍数.19．2．8★★设a 、b 是正整数，且满足关系式()()1111111111123456789a b +-=．求证：a b -是4的倍数． 解析 由已知条件可得11111a +与11111b -均为奇数，所以a 、b 均为偶数，又由已知条件()111112468a b ab -=+，因为ab 是4的倍数，24684617=⨯也是4的倍数，所以()11111a b ⨯-是4的倍数，故a b -是4的倍数．19.2.9★★9999和99!（注：99!123499=⨯⨯⨯⨯⨯，读作99的阶乘）能否表示成为99个连续的奇数的和？ 解析 （1）9999能．因为()()()()999898989898999998999699299992=-+-++-+++++()()989899969998+++．即9999能表示为99个连续奇数的和． （2）99!不能．因为99!12399=⨯⨯⨯⨯是一个偶数，而99个连续奇数之和仍为奇数，所以99!不能表示为99个连续奇数之和． 评注 如果答案是肯定的，我们常常将满足题意的例子举出来或造出来，这称为构造法． 如果答案是否定的，常常采用反证法，找出其中的矛盾． 19．2．10★★代数式rvz rey suz swx tuy tvx --++-． ①中，r 、s 、t 、u 、v 、w 、x 、y 、z 可以分别取1+或1-． （1）证明：代数式的值都是偶数； （2）求这个代数式所能取到的最大值． 解析 （1）①式中共有6项，每项的值都是奇数（1+或1-），所以它们的代数和为偶数．（2）显然，①式的值6≤，但它取不到6这个值，事实上，在rvz 、rwy -、suz -、swx 、tuy 、tvx -这六项中，至少有一项是1-，要证明这一点，将上面这6项相乘，积是 ()21rstuvwxyz -=-．所以六项中，至少有一项是1-，这样，六项和至多是514-=．在u 、x 、y 为1-，其他字母为1时，①式的值是4，所以①的最大值为4． 评注 本例中的代数式实际上是行列式 r s t u v w x y z的展开式，行列式是一个很有用的工具，在今后的学习中还会遇到．19.2.11★★★在n n ⨯（n 为奇数）方格表里的每一个方格中任意填上一个1+或1-，在每一列的下面写上该列所有数的乘积，在每行的右面写上该行所有数的乘积，求证：这个乘积的和不等于0． 解析 设每列下面的数为12 , , , n a a a ,每行右面的数为12 , , , n b b b ，依题意得1i a =+或1-，1i b =+或\1-， 1 , 2 , , i n =，若这2n 个乘积的和为0，即12120n n a a a b b b +++++++=，则这2n 个数中1+的个数与1-的个数一样多，都是n 个，但事实上，因为 1212n n a a a b b b =，()21212121n n n a a a bb b a a a ==．所以这2n 个数中1-的个数为偶数，即n 为偶数，矛盾．19．2．12★★在黑板上写上1，2，…，，，只要黑板上还有两个或两个以上的数，就擦去其中任意两个数a 和b ，并写上a b -，问最后黑板上剩下的数是奇数还是偶数？ 解析因为a b -与a b -有相同的奇偶性，而a b -又与a b +有相同的奇偶性，因此a b-与a b +具有相同的奇偶性．所以黑板上剩下的数的奇偶性与20012002122001*********⨯+++==⨯的奇偶性相同，是奇数．19.2.13★★把图中的圆圈任意涂上红色或蓝色，问有没有可能使得在同一条直线上的红圈数都是奇数？请说明理由．解析 如果每条线上红圈都是奇数个，那么5条线上的红圈数相加仍是奇数．但另一方面，由于每个圈都在两条直线上，因而相加时每个红圈都被计算了两次，从而相加的总和应该是偶数．两方面的结果是矛盾的．因此，不可能使同一条线上的红圈数都是奇数．19．2．14★★围棋盘上有1919⨯个交叉点，在交叉点上已经放满了黑子与白子，并且黑子与白子相间地放，即黑子（白子）的上、下、左、右都放着白子（黑子）．问能否把这些黑子全部移到原来白子的位置上，而白子也全移到原来的黑子的位置上？ 解析 不能．因为1919361⨯=是奇数，所以，必有奇数个白子，偶数个黑子；或者奇数个黑子，偶数个白子．即黑、白子数必然一奇一偶．奇数不可能等于偶数，所以无法使黑子与白子的位置对调．19.2.15★★参加会议的人，有不少互相握过手．握手的次数是奇数的那部分人，人数是奇数还是偶数？为什么？ 解析 由于每握一次手，握手的两个人，每一个都握了一次手．因此每握一次手，两个人握手次数的和就是2次．所以，全部与会的人握手的总次数必定是偶数．我们把参加会议的人分成两类，甲类握手次数是偶数，乙类握手次数是奇数，甲类人握手的总次数显然是偶数．注意甲类人握手的总次数加上乙类人握手的总次数等于全部与会的人握手的总次数，所以乙类人握手的总次数也应当是偶数．由于乙类人每人握手的次数都是奇数，而偶数个奇数相加，和才能为偶数，因此，乙类人必为偶数个，即握手次数是奇数的那部分人，人数是偶数．19．2．16★★设标有A 、B 、C 、D 、E 、F 、G 记号的七盏灯顺次排成一行，每盏灯安装一个开关．现在A 、C 、E 、G 四盏灯开着，其余三盏灯是关的．小刚从灯A 开始，顺次拉动开关.即从A 到G ，再从A 到G ，这样拉动了1999次开关后，哪几盏灯是开的？ 解析 一盏灯的开关被拉动奇数次后，改变状态，即开的变成关的，关的变成开的．一盏灯的开关被拉动偶数次后，不改变状态，即开的仍为开的，关的仍为关的．因此本题的关键是计算各盏灯被拉次数的奇偶性．由 199972854=⨯+，可知，A 、B 、C 、D 四盏灯的开关各被拉动了286次，而E 、F 、G 三盏灯的开关各被拉动了285次．所以，A 、B 、C 、D 四灯不改变状态，E 、F 、G 三灯改变状态．由于开始时A 、C 、E 、G 四灯是开着的．因此，最后A 、C 、F 三灯是开着的．19.2.17★★桌上放着七只杯子，杯口全朝上，每次翻转四个杯子．问能否经过若干次这样的翻动，使全部的杯子口都朝下？ 解析 不可能．。

初等数论的性质与定理总结初等数论是数论中的一个基础分支，研究整数的性质和整数运算规律。

本文将总结初等数论中的一些重要性质与定理。

一、整数的整除性质1. 整数的除法基本性质：对于任意整数a、b和非零整数c，存在唯一的整数q使得a = bq + c。

2. 整除关系的传递性：如果a能整除b，且b能整除c，则a能整除c。

3. 整除关系的辗转相除法：对于任意整数a和非零整数b，存在唯一的整数q和r使得a = bq + r（其中0 ≤ r < |b|）。

二、质数与合数1. 质数的定义：质数是指大于1且只能被1和自身整除的整数。

例如，2、3、5、7等都是质数。

2. 质因数分解定理：每个大于1的整数都可以唯一地表示为若干个质数的乘积。

3. 最大公约数与最小公倍数的性质：对于任意整数a和b，记a和b 的最大公约数为gcd(a, b)，最小公倍数为lcm(a, b)，则有以下性质： - gcd(a, b) = gcd(b, a)- gcd(a, 0) = |a|- lcm(a, b) = |ab| / gcd(a, b)三、模运算与同余1. 模运算的基本性质：对于任意整数a、b和正整数n，有以下性质：- (a + b) mod n = (a mod n + b mod n) mod n- (a - b) mod n = (a mod n - b mod n) mod n- (a * b) mod n = (a mod n * b mod n) mod n2. 同余关系的性质：对于任意整数a、b和正整数n，如果a与b模n同余（记作a ≡ b (mod n)），则有以下性质：- a + c ≡ b + c (mod n)- ac ≡ bc (mod n)- 如果a ≡ b (mod n)，则a^k ≡ b^k (mod n)对于任意正整数k四、费马小定理与欧拉定理1. 费马小定理：如果p是质数，a是任意正整数且p不整除a，则有a^(p-1) ≡ 1 (mod p)。

初等数论知识点数论是数学的一个重要分支，而初等数论则是数论中较为基础和入门的部分。

它主要研究整数的性质和相互关系，虽然看似简单，却蕴含着深刻的数学思想和广泛的应用。

一、整除整除是初等数论中最基本的概念之一。

如果整数 a 除以整数 b（b≠0），所得的商是整数且没有余数，我们就说 a 能被 b 整除，或者b 能整除 a，记作 b ｜ a。

例如，6 能被 3 整除，因为 6÷3 ＝ 2，没有余数；而 7 不能被 3 整除，因为 7÷3 ＝ 21，有余数 1。

整除具有一些基本性质，比如：1、如果 a ｜ b 且 b ｜ c，那么 a ｜ c。

2、如果 a ｜ b 且 a ｜ c，那么对于任意整数 m、n，有 a ｜（mb＋ nc)。

二、因数和倍数如果 a 能被 b 整除（b≠0），那么 b 就是 a 的因数，a 就是 b 的倍数。

一个数的因数是有限的，其中最大的因数是它本身；一个数的倍数是无限的，其中最小的倍数是它本身。

例如，12 的因数有1、2、3、4、6、12；12 的倍数有12、24、36、48三、质数和合数质数是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数。

合数则是指除了能被 1 和本身整除外，还能被其他数（0 除外）整除的自然数。

例如，2、3、5、7 是质数；4、6、8、9 是合数。

1 既不是质数也不是合数。

质数在数论中有着重要的地位，寻找大质数是密码学等领域中的关键问题。

四、公因数和最大公因数几个数公有的因数，叫做这几个数的公因数；其中最大的一个，叫做这几个数的最大公因数。

求最大公因数可以用辗转相除法。

例如，求 24 和 36 的最大公因数，36÷24 ＝ 112，24÷12 ＝ 2，所以24 和 36 的最大公因数是 12。

五、公倍数和最小公倍数几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。

第一章 整数的唯一分解定理第一节 整除性教学重点：应用带余数除法定义1 设a ，b 是整数，b ≠ 0，如果存在整数c ，使得a = bc成立，则称a 被b 整除，a 是b 的倍数，b 是a 的约数（因数或除数），并且使用记号b ∣a ；如果不存在整数c 使得a = bc 成立，则称a 不被b 整除，记为b |/a . 如果a = bc 里的c 不存在，我们就说b 不能整除a 或a 不被b 整除，记作b |/a . 定理1 （传递性）若a 是b 的倍数，b 是c 的倍数，则a 是c 的倍数， 也就是b |a,c|b ⇒c|a.证 b |a,c|b 就是说存在两个整数1a ，1b 使得111111,(),a ab b bc a a b c a b ===成立因此但是是一个整数，故c|a 定理2 若a ，b 都是m 的倍数，则a ±b 也是m 的倍数.证 a ，b 是m 的倍数的意义就是存在两个整数a 1 , b 1，使得111111,.(),a a m b b m a b a b m a b a b m ==±=±±±因此但是整数，故是的倍数 .定理3 若1212,,,,,,n n a a a m q q q 都是的倍数，是任意个整数，1122.n n q a q a q a m +++ 则是的倍数注：1、显然每个非零整数a 都有约数 ±1，±a ，称这四个数为a 的平凡约数，a 的另外的约数称为非平凡约数.2、若整数a ≠ 0，±1，并且只有约数 ±1和 ±a ，则称a 是素数（或质数）；否则称a 为合数.以后若无特别说明，素数总是指正素数.3、下面的结论成立：(ⅰ) a ∣b ⇔ ±a ∣±b ；·(ⅱ) a ∣b ，b ∣c ⇒ a ∣c ；(ⅲ) b ∣a i ，i = 1, 2, , k ⇒ b ∣a 1x 1 + a 2x 2 + + a k x k ，此处x i （i = 1, 2, , k ）是任意的整数；(ⅳ) b ∣a ⇒ bc ∣ac ，此处c 是任意的非零整数；(ⅴ) b ∣a ，a ≠ 0 ⇒ |b | ≤ |a |；b ∣a 且|a | < |b | ⇒ a = 0；(ⅴi) b ∣a ，a ≠ 0 ⇒ ba ∣a . 定理4(带余数除法) 设a 与b 是两个整数，b ≠ 0，则存在唯一的两个整数q 和r ，使得a = bq + r ，0 ≤ r < |b |. (1)证明 存在性 若b ∣a ，a = bq ，q ∈Z ，可取r = 0. 若b |/a ，考虑集合A = { a + kb ；k ∈Z },其中Z 表示所有整数的集合.在集合A 中有无限多个正整数，设最小的正整数是r = a + k 0b ，则必有0 < r < |b |， (2)否则就有r ≥ |b |. 因为b |/a ，所以r ≠ |b |. 于是r > |b |，即a + k 0b > |b |，a + k 0b - |b | > 0，这样，在集合A 中，又有正整数a + k 0b - |b | < r ，这与r 的最小性矛盾. 所以式(2)必定成立. 取q = - k 0知式(1)成立. 存在性得证.唯一性 假设有两对整数q '，r '与q ''，r ''都使得式(1)成立，即a = q ''b + r '' = q 'b + r '，0 ≤ r ', r '' < |b |，则(q '' - q ')b = r ' - r ''，|r ' - r ''| < |b |， (3)因此r ' - r '' = 0，r ' = r ''，再由式(3)得出q ' = q ''，唯一性得证. 证毕3、定义2 称式(1)中的q 是a 被b 除的不完全商，r 是a 被b 除的余数，也叫最小非负剩余，记作r a b =><.第二节 最大公因数与辗转相除法第三节 最小公倍数教学目的：1、掌握最大公因数与最小公倍数性质；2、掌握辗转相除法；3、会求最大公因数与最小公倍数.教学重点：最大公因数与最小公倍数性质教学难点：辗转相除法一、最大公因数定义 设12,,,2).n a a a n n d ≥ 是（个整数若整数是它们之中每一个的因数， 12,,,n d a a a 那么就叫作的一个公因数.整数a 1, a 2, , a k 的公共约数称为a 1, a 2, , a k 的公约数.不全为零的整数a 1, a 2, , a k 的公约数中最大的一个叫做a 1, a 2, , a k 的最大公约数（或最大公因数），记为(a 1, a 2, , a k ).如果(a 1, a 2, , a k ) = 1，则称a 1, a 2, , a k 是互素的（或互质的）；如果(a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j ，则称a 1, a 2, , a k 是两两互素的（或两两互质的）.显然，a 1, a 2, , a k 两两互素可以推出(a 1, a 2, , a k ) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2.定理1 12,,,n a a a n 若是任意个不全为零的整数，则1212i ,,,,,n n a a a a a a （）与的公因数相同； 1212ii ,,,,,.n n a a a a a a = （）(）（）证 12,,,.,1,2,,,n i d a a a d a i n = 设是的任一公因数由定义12,1,2,,,,,i n d a i n d a a a = 因而故是的一个公因数，121,2,,,.n n a a a a a 同法可证，的任一个公因数都是，a 的一个公因数 121,2,,,n n a a a a a 故与a 有相同的公因数.定理2 若b 是任一正整数，则（i ）0与b 的公因数就是b 的因数， 反之，b 的因数也就是0与b 的公因数 . (ii) (0,b)=b .证 显然0与b 的公因数是b 的公因数 .由于任何非零整数都是0的因数， 故b 的因数也就是0，b 的公因数，于是（i ）得证.其次，我们立刻知道b 的最大因数是b ；而0，b 的最大公因数是b 的最大公因数，故（0，b ）=b.推论2.1 若b 是任一非零整数，则（0，b ）= b .定理3 ,,,,,,)(,).a b c a bq c q a b b c a b b c =+=设是任意三个不全为零的整数，且其中是非零整数，则与有相同的公因数，因而（ 定理4 ,(,)a b a b 若是任意两个整数，则就是a = bq 1 + r 1， 0 < r 1 < |b |，b = r 1q 2 + r 2， 0 < r 2 < r 1 ，r k - 1 = r k q k + 1 + r k + 1，0 < r k + 1 < r k ， (1)r n - 2 = r n - 1q n + r n ， 0 < r n < r n-1 ，r n - 1 = r n q n + 1 .中的最后一个不等于零的余数，即得(,)n a b r =推论4.1 ,(,).a b a b 的公因数与的因数相同例（1）1859,1573185928621431859143.a b =-=-⨯⨯=⨯-=由定理得（，1573）=（1859,1573）.1859=11573+2861573=5286+143所以（，1573）=（1859,1573）例（2）169,121484812532512322311212211.a b ==⨯⨯=⨯+=⨯+=⨯+=⨯=由定理得169=1121+48121=2+25所以（169,121）定理5 ,i (,),a b a b a b δδδδ设是任意两个不全为零的整数，（）若m 是任一正整数，则(am,bm)=(a,b)m.(ii)若是a,b 的任一公因数，则（,）= 特别地, )(),(,),(b a b b a a = 1. 定理6 1212,,,,,,).n n n a a a n a a a d = 若是个整数，则(二、最小公倍数1、定义 整数a 1, a 2, , a k 的公共倍数称为a 1, a 2, , a k 的公倍数. a 1, a 2, , a k 的正公倍数中的最小的一个叫做a 1, a 2, , a k 的最小公倍数，记为[a 1, a 2, , a k ].2、定理1 下面的等式成立：(ⅰ) [a , 1] = |a |，[a , a ] = |a |；(ⅱ) [a , b ] = [b , a ]；(ⅲ) [a 1, a 2, , a k ] = [|a 1|, |a 2| , |a k |]；(ⅳ) 若a ∣b ，则[a , b ] = |b |.3、定理2 对任意的正整数a ，b ，有[a , b ] =),(b a ab . 证明：设m 是a 和b 的一个公倍数，那么存在整数k 1，k 2，使得m = ak 1，m = bk 2，因此ak 1 = bk 2 . (1)于是21),(),(k b a b k b a a =. 由于)(),(,),(b a b b a a = 1，所以 t b a b k k b a b ),(),(11|=即，， 其中t 是某个整数. 将上式代入式(1)得到m =),(b a ab t . (2) 另一方面，对于任意的整数t ，由式(2)所确定的m 显然是a 与b 的公倍数，因此a 与b 的公倍数必是式(2)中的形式，其中t 是整数.当t = 1时，得到最小公倍数[a , b ] =),(b a ab . 推论1 两个整数的任何公倍数可以被它们的最小公倍数整除.证明 由式(2)可得证.这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数.推论2 设m ，a ，b 是正整数，则[ma , mb ] = m [a , b ].证明 由定理2及前面的定理2的推论得到[ma , mb ] =),(),(),(22b a mab b a m ab m mb ma ab m === m [a , b ]. 证毕4、定理3 对于任意的n 个整数a 1, a 2, , a n ，记[a 1, a 2] = m 2，[m 2, a 3] = m 3， ，[m n -2, a n -1] = m n -1，[m n -1, a n ] = m n ，则[a 1, a 2, , a n ] = m n .证明：我们有m n = [m n -1, a n ] ⇒ m n -1∣m n ，a n ∣m n ，m n -1 = [m n -2, a n -1] ⇒ m n -2∣m n -1∣m n ，a n ∣m n ，a n -1∣m n -1∣m n ，m n -2 = [m n -3, a n -2] ⇒ m n -3∣m n -2∣m n ，a n ∣m n ，a n -1∣m n ，a n -2∣m n ，m 2 = [a 1, a 2] ⇒ a n ∣m n ， ，a 2∣m n ，a 1∣m n ，即m n 是a 1, a 2, , a n 的一个公倍数.另一方面，对于a 1, a 2, , a n 的任何公倍数m ，由定理2的推论及m 2, , m n 的定义，得m 2∣m ，m 3∣m ， ，m n ∣m .即m n 是a 1, a 2, , a n 最小的正的公倍数. 证毕推论 若m 是整数a 1, a 2, , a n 的公倍数，则[a 1, a 2, , a n ]∣m .定理4 整数a 1, a 2, , a n 两两互素，即(a i , a j ) = 1，1 ≤ i , j ≤ n ，i ≠ j的充要条件是[a 1, a 2, , a n ] = a 1a 2 a n . (3)证明：必要性 因为(a 1, a 2) = 1，由定理2得到[a 1, a 2] =),(2121a a a a = a 1a 2 . 由(a 1, a 3) = (a 2, a 3) = 1及前面的定理4推论得到(a 1a 2, a 3) = 1，由此及定理3得到[a 1, a 2, a 3] = [[a 1, a 2], a 3] = [a 1a 2, a 3] = a 1a 2a 3 .如此继续下去，就得到式(3).充分性 用归纳法证明. 当n = 2时，式(3)成为[a 1, a 2] = a 1a 2. 由定理2a 1a 2 = [a 1, a 2] =),(2121a a a a ⇒ (a 1, a 2) = 1， 即当n = 2时，充分性成立.假设充分性当n = k 时成立，即[a 1, a 2, , a k ] = a 1a 2 a k ⇒ (a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j .对于整数a 1, a 2, , a k , a k + 1，使用定理3中的记号，由定理3可知[a 1, a 2, , a k , a k + 1] = [m k , a k + 1]. (4)其中m k = [a 1, a 2, , a k ].因此，如果[a 1, a 2, , a k , a k + 1] = a 1a 2 a k a k + 1，那么，由此及式(4)得到[a 1, a 2, , a k , a k + 1] = [m k , a k + 1] =),(11++k k k k a m a m = a 1a 2 a k a k + 1， 即),(1+k k k a m m = a 1a 2 a k ， 显然m k ≤ a 1a 2 a k ，(m k , a k + 1) ≥ 1.所以若使上式成立，必是(m k , a k + 1) = 1， (5)并且m k = a 1a 2 a k . (6)由式(6)与式(5)推出(a i , a k + 1) = 1，1 ≤ i ≤ k ； (7)由式(6)及归纳假设推出(a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j . (8)综合式(7)与式(8)，可知当n = k + 1时，充分性成立. 由归纳法证明了充分性. 证毕三、辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid 算法.它是数论中的一个重要方法，在其他数学分支中也有广泛的应用.1、定义1 下面的一组带余数除法，称为辗转相除法.设a 和b 是整数，b ≠ 0，依次做带余数除法：a = bq 1 + r 1， 0 < r 1 < |b |，b = r 1q 2 + r 2， 0 < r 2 < r 1 ，r k - 1 = r k q k + 1 + r k + 1，0 < r k + 1 < r k ， (1)r n - 2 = r n - 1q n + r n ， 0 < r n < r n-1 ，r n - 1 = r n q n + 1 .由于b 是固定的，而且|b | > r 1 > r 2 > ，所以式(1)中只包含有限个等式.下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计.2、引理1 用下面的方式定义Fibonacci 数列{F n }：F 1 = F 2 = 1，F n = F n - 1 + F n - 2，n ≥ 3，那么对于任意的整数n ≥ 3，有F n > α n - 2， (2)其中α =251+.证明：容易验证α 2 = α + 1.当n = 3时，由F 3 = 2 >251+= α 可知式(2)成立.假设式(2)对于所有的整数k ≤ n （n ≥ 3）成立，即F k > α k - 2，k ≤ n ，则F n + 1 = F n + F n - 1 > α n - 2 + α n - 3 = α n - 3(α + 1) = α n - 3α 2 = α n - 1，即当k = n + 1时式(2)也成立.由归纳法知式(2)对一切n ≥ 3成立.证毕. 定理11(1),1,,;k k k k a P b r k n --=-= 若a,b 是任意两个正整数，则Q其中 0111201121,,,0,1,,k k k k k k k k P P q P q P P Q Q Q q Q Q ----===+===+ 其中k=2,,n.推论1.1若a,b 是任意两个不全为零的整数，则存在两个整数s,t 使得as+bt=(a,b).定理2 若a,b,c 是三个整数，且(a,c)=1.则i （）ab,c 与b,c 有相同的公因数，ii （） (ab,c)=(b,c),,.b c 上面假定了至少有一不为零推论2.1 ,.ab c b 若（a,c)=1,c 则推论2.2 1212,,,,,,.n m a a a b b 设及b 是任意两组整数1212,,,,,,.n m a a a b b 若前一组中任意整数与后一组中任意整数互质，则与b 互质例2 用辗转相除法求(125, 17)，以及x ，y ，使得125x + 17y = (125, 17).解：做辗转相除法：125 = 7⋅17 + 6，q 1 = 7，r 1 = 6，17 = 2⋅6 + 5， q 2 = 2，r 2 = 5，6 = 1⋅5 + 1， q 3 = 1，r 3 = 1，5 = 5⋅1， q 4 = 5.由定理4，(125, 17) = r 3 = 1.利用定理2计算（n = 3）P 0 = 1，P 1 = 7，P 2 = 2⋅7 + 1 = 15，P 3 = 1⋅15 + 7 = 22，Q 0 = 0，Q 1 = 1，Q 2 = 2⋅1 + 0 = 2，Q 3 = 1⋅2 + 1 = 3，取x = (-1)3 - 1Q 3 = 3，y = (-1)3P 3 = -22，则125⋅3 + 17⋅(-22) = (125, 17) = 1.例3 求(12345, 678).解：(12345, 678) = (12345, 339) = (12006, 339) = (6003, 339)= (5664, 339) = (177, 339) = (177, 162) = (177, 81)= (96, 81) = (3, 81) = 3.例4 在m 个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n （n < m ）个盒子中各放一个硬币.证明：若(m , n ) = 1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币.解：由于(m , n ) = 1，所以存在整数x ，y ，使得mx + ny = 1. 因此对于任意的自然数k ，有1 + m (-x + kn ) = n (km + y )，这样，当k 充分大时，总可找出正整数x 0，y 0，使得1 + mx 0 = ny 0 .上式说明，如果放y 0次（每次放n 个），那么在使m 个盒子中各放x 0个后，还多出一个硬币.把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1. 因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同.四、小结.第四节 素数、整数的唯一分解定理教学目的：1、掌握素数的一系列性质；2、理解并掌握唯一分解定理.教学重点：素数的性质及唯一分解定理的证明及应用教学难点：唯一分解定理的证明及应用教学课时：4课时教学过程一、素数1、定义 大于1的整数，如果只有平凡因子，就叫素数，否则叫合数.2、定理1 设a 是任意大于1的整数，则a 除1以外的最小正因子p 是素数，并且当a 是合数时，则a p ≤ .3、定理2 设p 是素数，a 是任意整数，则a p |或1),(=a p .4、定理3 设p 是素数，p|ab , 则p|a 或p|b.5、定理4 素数有无穷多个.6、定理2 形如4n-1型的素数有无穷多个.例1 写出不超过100的所有的素数。

初等数论（1）----数的整除初等数论又称初等整数论，它的研究对象是整数集。

整数是小学就接触的一类数，但是关于数论的问题却是最难解决的。

1、整数的离散性：任何两个整数,x y 之间的距离至少为1，因此有不等式1x y x y <⇔+≤。

2、整数的奇偶性：将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m （m ∈Z ），任一奇数可表为2m+1或2m －1的形式.关于奇数和偶数，有下面的性质：（1）奇数不会同时是偶数；两个连续整数中必是一个奇数一个偶数；（2）奇数个奇数和是奇数；偶数个奇数的和是偶数；任意多个偶数的和是偶数；（3）奇数±奇数=偶数；偶数±偶数=偶数；奇数±偶数=奇数；偶数×偶数=偶数；奇数×偶数=偶数；奇数×奇数=奇数；（4）两个整数的和与这两个整数的差有相同的奇偶性；（5）奇数的平方都可表为81m +形式，偶数的平方都可表为8m 或84m +的形式（m ∈Z ）. （6）任意两个整数的平方和被4除余数不可能是3.（7）任意两个整数的平方差被4除余数不可能是2.以上性质简单明了，解题时如果能巧妙应用，常常可以出奇制胜.数的整除一、知识点讲解1、设,a b 是整数，0b ≠，若存在整数q ，使得a bq =，则称b 整除a ，记为|b a ，并称b 是a 的一个约数（或因子），而a 是b 的倍数。

如果不存在上述的整数q ，则称b 不整除a ，记作†b a 。

补充：关于整除的一些小结论：一个整数被2，3，4，5，7，8，9，11，13等整除的特征.（1）一个整数能被2或5整除的特征是：这个数的末位数字能被2或5整除。

（2）一个整数能被3或9整除的特征是：这个数的各位数之和能被3或9整除。

（3）一个整数能被4或25整除的特征是：这个数的末两位数能被4或25整除。

（4）一个整数能被8或125整除的特征是：这个数的末三位数能被8或125整除。

初等数论“整除”【摘要】本文主要讲述整除和有关整除问题【关键词】整除整除问题是数学学习的一大方面，无论小学，中学，还是高中，甚至大学数学都有关于整除的问题。

理解掌握整除的概念、性质及某些特殊数的整除特征，可以简单快捷地解决许多整除问题。

现在对整除问题做下整理，以方便关于整除问题的学习，来了解、深入的探讨整除问题。

一、整除的定义：当两个整数a和b（b≠0），a被b除的余数为零时（商为整数），则称a被b整除或b整除a，也把a叫做b的倍数，b叫a的约数，记作b|a，如果a被b除所得的余数不为零，则称a不能被b整除，或b不整除a，记作b a.注：a , b作除数的其一为0则不叫整除。

二、数的整除性质：(1)对称性：若甲数能被乙数整除，乙数也能被甲数整除，那么甲、乙两数相等。

记作：a|b,b|a,则a=b。

( 2)传递性：若甲数能被乙数整除，乙数能被丙数整除，那么甲数能被丙数整除。

记作：若a|b,b|c,则a|c。

(3) 若两个数能被一个自然数整除，那么这两个数的和与差都能被该自然数整除。

记作：如果b∣a，b∣c那么b∣a±c．(4) 几个数相乘，若其中有一个因子能被某一个数整除，那么它们的积也能被该数整除。

(5) 若一个数能被两个互质数中的每一个数整除，那么这个数也能分别被这两个互质数的积整除。

记作：若a|b,c|b,(a,c)=1, 则ac|b。

(6) 若一个数能被两个互质数的积整除，那么，这个数也能分别被这两个互质数整除。

记作：若ac|b,(a,c)=1, 则a|b,c|b。

(7) 若一个质数能整除两个自然数的乘积，那么这个质数至少能整除这两个自然数中的一个。

(8) 若a|b,m≠0,则am|bm。

(9) 若am|bm,m≠0,则a|b。

（10）若c|a，c|b，则c|（ma+nb），其中m、n为任意整数（这一性质还可以推广到更多项的和）三、整除特征（1）1与0的特性：1是任何整数的约数，即对于任何整数a，总有1|a.0是任何非零整数的倍数，a≠0,a为整数，则a|0.（2）若一个整数的末位是0、2、4、6或8，则这个数能被2整除。

第四讲初等数论1——整除性本讲概述数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容.初等数论是数学竞赛四大模块中较难以掌握的模块之一，在数学竞赛中占据极其重要的位置.特别是联赛改制以后，二试必考一道50分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键.初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过.但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中，大家将复习小学初中阶段的数论知识，并将其中的很多知识更为理论化、系统化.高中的数论问题难度也会明显增高. 但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题.由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论.如果不特别说明，本讲中所有字母均代表正整数.一、整除1．整除的定义两个整数a和b(b≠0)，若存在整数k，使得a=bk，我们称a能被b整除，记作b|a．此时把a叫做bŒ．的倍数，b叫做a的约数．如果a除以b的余数不为零，则称a不能被b整除，或b不整除a，记作b a 2．数的整除特征（1）1与0的特性：1是任何整数的约数，即对于任何整数a，总有1|a．0是任何非零整数的倍数，a≠0，a为整数，则a|0．（2）能被2，5；4，25；8，125；3，9；11，7，13整除的数的特征：能被2整除的数的特征：个位为0，2，4，6，8的整数能被2整除，我们记为2k(k为整数)．能被5整除的数的特征：个位数为0或5的整数必被5整除，我们记为5k(k为整数)．能被4、25整除的数的特征：末两位数字组成的两位数能被4（25）整除的整数必能被4（25）整除．能被8，125整除的数的特征：末三位数字组成的三位数能被8（125）整除的整数必能被8（125）整除．能被3，9整除的数的特征：各个数位上数字之和能被3或9整除的整数必能被3或9整除．能被11整除的数的特征：一个整数的奇数位数字之和与偶数位数字之和的差如果是11的倍数，则这个数就能被11整除．能被7，11，13整除的数的特征：一个三位以上的整数能否被7（11或13）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11或13）整除．3．整除的几条性质（1）自反性：a|a(a≠0)（2）对称性：若a|b, b|a，则a=b（3）传递性：若a|b, b|c，则a|c（4）若a|b, a|c，则a|(b, c)（5）若a|b, m≠0，则am|bm（6）若am|bm, m≠0，则a|b（7）若a|b, c|b, (a, c)=1，则ac|b高一·联赛班·第4讲·学生版2 二、带余除法对于任一整数a 及大于1的整数m ，存在唯一的一对整数q, r (0≤r<m)，使得a=qm+r 成立，这个式子称为带余除法式。