王进明初等数论习题解答2012.3第九版

初等数论王进明答案【篇一：王进明__初等数论_习题解答】s=txt>1．已知两整数相除，得商12，余数26，又知被除数、除数、商及余数之和为454．求被除数.解：a?12b?26,a?b?12?26?454,12b?26?b?12?26?454,(12?1)b?454?12?26?26?390,b=30, 被除数a=12b+26=360+26=386.这题的后面部分是小学数学的典型问题之一——“和倍” 问题。

2．证明：(1) 当n∈z且n?9q?r(0?r?9)时，r只可能是0,1,8;证：把n按被9除的余数分类，即：若n=3k, k∈z，则n?27k, r=0；若n=3k +1, k∈z，则n?(3k)?3(3k)?3(3k)?1?9k(3k?3k?1)?1,r=1；若n=3k－1, k∈z，则n?(3k)?3(3k)?3(3k)?1?9(3k?3k?k?1)?8,r=8. 332323322333n3n2n??的值是整数。

(2) 当 n∈z时，326n3n2n2n3?3n2?n32??=证因为，只需证明分子2n?3n?n是6的倍数。

32662n3?3n2?n?n(2n2?3n?1)?(n?1)n(2n?1)?(n?1)n(n?2?n?1)=n(n?1)(n?2)?(n?1)n(n?1).由k! 必整除k个连续整数知：6 |n(n?1)(n?2),6 |(n?1)n(n?1).或证：2!|(n?1)n, (n?1)n必为偶数.故只需证3|(n?1)n(2n?1).若3|n, 显然3|(n?1)n(2n?1)；若n为3k +1, k∈z，则n－1是3的倍数，得知(n?1)n(2n?1)为3的倍数；若n为3k－1, k∈z，则2n－1=2(3k－1)－1=6k-3, 2n－1是3的倍数.综上所述，(n?1)n(2n?1)必是6的倍数,故命题得证。

(3) 若n为非负整数，则133|(11n+2+122n+1)．(4)当m，n，l∈n+时，(m?n?l)!的值总是整数 m!n!l!(n?l?1)(n?l)(n?l?1)(l?1)?l! 证明：(m?n?l)!=(m?n?l)(m?n?l?1)由k!必整除k个连续整数知：m!|(m?n?l)(m?n?l?1)n! |(n?l)(n?l?1)(n?l?1), (l?1)，从而由和的整除性即证得命题。

习题参考答案第一章习题一1. (ⅰ) 由a∣b知b = aq，于是b = (-a)(-q)，-b = a(-q)及-b = (-a)q，即-a∣b，a∣-b及-a∣-b。

反之，由-a∣b，a∣-b及-a∣-b也可得a∣b；(ⅱ) 由a∣b，b∣c知b = aq1，c = bq2，于是c = a(q1q2)，即a∣c；(ⅲ) 由b∣a i知a i= bq i，于是a1x1+a2x2+ +a k x k = b(q1x1+q2x2+ +q k x k)，即b∣a1x1+a2x2+ +a k x k；(ⅳ) 由b∣a知a = bq，于是ac = bcq，即bc∣ac；(ⅴ) 由b∣a知a = bq，于是|a| = |b||q|，再由a ≠ 0得|q| ≥ 1，从而|a| ≥ |b|，后半结论由前半结论可得。

2. 由恒等式mq+np = (mn+pq) - (m-p)(n-q)及条件m-p∣mn+pq可知m-p∣mq+np。

3. 在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，则a, a+ 1, , a+ 9, a+ 19的数字和为s, s+ 1, , s+ 9, s+ 10，其中必有一个能被11整除。

4. 设不然，n1 = n2n3，n2≥p，n3≥p，于是n = pn2n3≥p3，即p≤3n，矛盾。

5. 存在无穷多个正整数k，使得2k+ 1是合数，对于这样的k，(k+ 1)2不能表示为a2+p的形式，事实上，若(k+ 1)2 = a2+p，则(k+ 1 -a)( k+ 1 +a) = p，得k+ 1 -a = 1，k+ 1 +a = p，即p = 2k+ 1，此与p 为素数矛盾。

第一章习题二1. 验证当n =0,1，2，… ,11时，12|f(n)。

2.写a = 3q1+r1，b = 3q2+r2，r1, r2 = 0, 1或2，由3∣a2+b2 = 3Q+r12+r22知r1 = r2 = 0，即3∣a且3∣b。

《初等数论》习题解答作业3一．选择题1，B 2，C 3，D 4，A二．填空题1，自反律 2，对称性 3，13 4，十进位 5，3 6，2 7，1三．计算题1， 解：由Euler 定理知：（a,m ）=1 则 a φ (m)≡1 (modm)∵(3,100)=1. 3φ (100)=340≡13360≡13364=3360×34≡34 (mod 100)∴34≡81 (mod 100)故：3364的末两位数是81.2, 解：132=169≡4 （mod 5）134=16≡1 (mod 5)1316≡1 (mod 5)1332≡1 (mod 5)1348≡1 (mod 5)1350=1348×1321350≡132≡4 (mod 5)3, 解： ∵(7,9)=1. ∴只有一个解7X －5≡9Y (mod 9)7X －9Y ≡5 (mod 9)解之得：X=2，Y=1∴X=2+9≡11=2 (mod 9)4, 解： ∵（24，59）=1 ∴只有一个解24X ≡7 (mod 59)59Y ≡﹣7 (mod 24)11Y=﹣7 (mod 24)24Z=7 (mod 11)2Z=7 (mod 11)11W=﹣7 (mod 2)W =﹣7 (mod 2)W=﹣1 (mod 2)Z=2711+-= －2 Y=117242-⨯-=－5X=247595+⨯-=2288-=－12 =47(mod59)5 解 ∵（45，132）=3，∴同余式有三个解。

45X ≡21（mod32）15x ≡7 (mod44)44y ≡-7 (mod15)14y ≡-7 (mod15)15z ≡-7 (mod14)z ≡7 (mod14) y=147715-⨯=7 x=157744+⨯=21 ∴x=21+31322⨯=109 (mod132) x=21+31321⨯=65 (mod132) x=21 (mod132)6、解 ∵（12，45）=3, ∴同余式有三个解。

《初等数论》第三版习题解答第一章整数的可除性§1整除的概念·带余除法1．证明定理3定理3若a1，a2，，an都是m得倍数，q1，q2，，qn是任意n个整数，则q1a1q2a2证明：qnan是m得倍数．a1,a2,an都是m的倍数。

pn使a1p1m,a2p2m,存在n个整数p1,p2,又q1,q2,,anpnm,qn是任意n个整数qnanq1a1q2a2q1p1mq2p2m(p1q1q2p2即q1a1q2a2qnpnmqnpn)mqnan是m的整数2．证明3|n(n1)(2n1)证明n(n1)(2n1)nn(1n)(2nn(n1)(n2)n(1n)n(又n(n1)(n2)，(n1)n(n2)是连续的三个整数故3|n(n1)(n2),3|(n1)n(n1)3|n(n1)(n2)(n1)n(n1)从而可知3|n(n1)(2n1)3．若a某0by0是形如a某by（某，y是任意整数，a，b是两不全为零的整数）的数中最小整数，则(a某0by0)|(a某by)．1/77证：a,b不全为0在整数集合Sa某by|某,yZ中存在正整数，因而有形如a某by的最小整数a某0by0某,yZ，由带余除法有a某by(a某0by0)qr,0ra某0by0则r(某某0q)a(yy0q)bS，由a某0by0是S中的最小整数知r0a某0by0|a某bya某0by0|a某by（某,y为任意整数）a某0by0|a,a某0by0|ba某0by0|(a,b).又有(a,b)|a，(a,b)|b(a,b)|a某0by0故a某0by0(a,b) 4．若a，b是任意二整数，且b0，证明：存在两个整数，t使得abt,|t||b|2成立，并且当b是奇数时，，t是唯一存在的．当b是偶数时结果如何？证：作序列即存在一个整数q，使2222若b0则令,tabaq2bqb，则同样有t22(ii)当q为奇数时，若b0则令q1q1,tabab，则有222/77下证唯一性当b为奇数时，设abtb1t1则tt1b(1)b而tbb,t1tt1tt1b矛盾故1,tt122b为整数2当b为偶数时，,t不唯一，举例如下：此时3bbbbbb1b2(),t1,t122222§2最大公因数与辗转相除法1．证明推论4.1推论4.1a，b的公因数与（a，b）的因数相同．证：设d是a，b的任一公因数，d|a，d|b由带余除法abq1r1,br1q2r2,rnqn1,0rn1rnrn1(a,b)rnd|abq1r1，d|br1q2r2，┄,d|rn2rn1qnrn(a,b),即d是(a,b)的因数。

《初等数论》第三版习题解答第⼀章整数的可除性§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 b 00(,)|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．已知两整数相除，得商12，余数26，又知被除数、除数、商及余数之和为454．求被除数.解：1226,1226454,a b a b =++++=12261226454,b b ++++=(121)454122626390,b +=---=b =30, 被除数a =12b +26=360+26=386.这题的后面部分是小学数学的典型问题之一——“和倍” 问题。

2．证明：(1) 当n ∈Z 且39(09)n q r r =+≤<时，r 只可能是0,1,8;证：把n 按被9除的余数分类，即：若n=3k, k ∈Z ，则3327n k =, r=0；若n=3k +1, k ∈Z ，则3322(3)3(3)3(3)19(331)1n k k k k k k =+++=+++,r=1； 若n=3k －1, k ∈Z ，则33232(3)3(3)3(3)19(331)8n k k k k k k =-+-=-+-+,r=8. (2) 当 n ∈Z 时，32326n n n -+的值是整数。

证 因为32326n n n -+=32236n n n -+，只需证明分子3223n n n -+是6的倍数。

32223(231)(1)(21)n n n n n n n n n -+=-+=--(1)(21)n n n n =--++=(1)(2)n n n --+(1)(1)n n n -+.由k ! 必整除k 个连续整数知：6 |(1)(2)n n n --,6 |(1)(1)n n n -+.或证：2!|(1)n n -, (1)n n -必为偶数.故只需证3|(1)(21)n n n --.若3|n, 显然3|(1)(21)n n n --；若n 为3k +1, k ∈Z ，则n －1是3的倍数，得知(1)(21)n n n --为3的倍数；若n 为3k －1, k ∈Z ，则2n －1=2(3k －1)－1=6k-3, 2n －1是3的倍数.综上所述，(1)(21)n n n --必是6的倍数,故命题得证。

第一章整除理论整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节数的整除性定义1设a，b是整数，b≠ 0，如果存在整数c，使得a = bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b∣a；如果不存在整数c使得a = bc成立，则称a不被b 整除，记为b|/a。

显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1下面的结论成立：(ⅰ) a∣b⇔±a∣±b；(ⅱ) a∣b，b∣c⇒a∣c；(ⅲ) b∣a i，i = 1, 2, , k⇒b∣a1x1+a2x2+ +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。

证明留作习题。

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

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

定理2任何大于1的整数a都至少有一个素约数。

证明若a是素数，则定理是显然的。

若a 不是素数，那么它有两个以上的正的非平凡约数，设它们是d 1, d 2, , d k 。

不妨设d 1是其中最小的。

若d 1不是素数，则存在e 1 > 1，e 2 > 1，使得d 1 = e 1e 2，因此，e 1和e 2也是a 的正的非平凡约数。

这与d 1的最小性矛盾。

所以d 1是素数。

证毕。

推论 任何大于1的合数a 必有一个不超过a 的素约数。

证明 使用定理2中的记号，有a = d 1d 2，其中d 1 > 1是最小的素约数，所以d 12 ≤ a 。

《初等数论》习题集第1章第 1 节1. 证明定理1。

2. 证明：若m - p ∣mn + pq ，则m - p ∣mq + np 。

3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。

4. 设p 是n 的最小素约数，n = pn 1，n 1 > 1，证明：若p >3n ，则n 1是素数。

5. 证明：存在无穷多个自然数n ，使得n 不能表示为a 2 + p （a > 0是整数，p 为素数）的形式。

第 2 节1. 证明：12∣n 4 + 2n 3 + 11n 2 + 10n ，n ∈Z 。

2. 设3∣a 2 + b 2，证明：3∣a 且3∣b 。

3. 设n ，k 是正整数，证明：n k 与n k + 4的个位数字相同。

4. 证明：对于任何整数n ，m ，等式n 2 + (n + 1)2 = m 2 + 2不可能成立。

5. 设a 是自然数，问a 4 - 3a 2 + 9是素数还是合数？6. 证明：对于任意给定的n 个整数，必可以从中找出若干个作和，使得这个和能被n 整除。

第 3 节1. 证明定理1中的结论(ⅰ)—(ⅳ)。

2. 证明定理2的推论1, 推论2和推论3。

3. 证明定理4的推论1和推论3。

4. 设x ，y ∈Z ，17∣2x + 3y ，证明：17∣9x + 5y 。

5. 设a ，b ，c ∈N ，c 无平方因子，a 2∣b 2c ，证明：a ∣b 。

6. 设n 是正整数，求1223212C ,,C ,C -n n n n 的最大公约数。

第 4 节1. 证明定理1。

2. 证明定理3的推论。

3. 设a ，b 是正整数，证明：(a + b )[a , b ] = a [b , a + b ]。

4. 求正整数a ，b ，使得a + b = 120，(a , b ) = 24，[a , b ] = 144。

5. 设a ，b ，c 是正整数，证明：),)(,)(,(),,(],][,][,[],,[22a c c b b a c b a a c c b b a c b a =。

初等数论练习题答案原点教育培训学校初等数论练习题一一、填空题1、d(2420)=12; ϕ(2420)=_880_2、设a,n 是大于1的整数，若a n -1是质数，则a=_2.3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1,0,1,2,3,4}.4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。

5、不定方程18x-23y=100的通解是x=900+23t ，y=700+18t t ∈Z 。

.6、分母是正整数m 的既约真分数的个数为_ϕ(m )_。

7、18100被172除的余数是_256。

8、⎪⎭⎫ ⎝⎛10365 =-1。

9、若p 是素数，则同余方程x p - 1 ≡1(mod p )的解数为 p-1 。

二、计算题1、解同余方程：3x 2+11x -20 ≡ 0 (mod 105)。

解：因105 = 3⋅5⋅7，同余方程3x 2+11x -20 ≡ 0 (mod 3)的解为x ≡ 1 (mod 3)， 同余方程3x 2+11x -38 ≡ 0 (mod 5)的解为x ≡ 0，3 (mod 5)， 同余方程3x 2+11x -20 ≡ 0 (mod 7)的解为x ≡ 2，6 (mod 7)， 故原同余方程有4解。

作同余方程组：x ≡ b 1 (mod 3)，x ≡ b 2 (mod 5)，x ≡ b 3 (mod 7)，其中b 1 = 1，b 2 = 0，3，b 3 = 2，6，由孙子定理得原同余方程的解为x ≡ 13，55，58，100 (mod 105)。

2、判断同余方程x 2≡42(mod 107)是否有解？11074217271071107713231071107311072107710731072107732107422110721721107213)(=∴-=-=-==-=-=-==⨯⨯≡-•--•-）（）（）（）（），（）（）（）（），（）（））（）（（）（解：故同余方程x 2≡42(mod 107)有解。

《初等数论》版习题解答第⼀章整数的可除性§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)(2n n n n n n n ++=+++-(1)(2)(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,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 b 00(,)|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 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 ++==-=-，则有1102222b b q q t a bs a b a b t ++-≤=-=-=-<∴≤ 若 0b <，则令11,22q q s t a bs a b ++=-下证唯⼀性当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 的因数。

g3.1092 排列与组合的综合问题一、知识梳理1.排列、组合都是研究事物在某种给定的模式下所有可能的配置的数目问题，它们之间的主要区别在于是否要考虑选出元素的先后顺序，不需要考虑顺序的是组合问题，需要考虑顺序的是排列问题，排列是在组合的基础上对入选的元素进行排队，因此，分析解决排列组合问题的基本思维是“先组，后排”.2.解排列组合的应用题，要注意四点：（1）仔细审题，判断是组合问题还是排列问题；要按元素的性质分类，按事件发生的过程进行分步.（2）深入分析、严密周详，注意分清是乘．还是加．，既不少也不多，辩证思维，多角度分析，全面考虑，这不仅有助于提高逻辑推理能力，也尽可能地避免出错.（3）对于附有条件的比较复杂的排列组合应用题，要周密分析，设计出合理的方案，把复杂问题分解成若干简单的基本问题后应用分类计数原理或分步计数原理来解决.（4）由于排列组合问题的答案一般数目较大，不易直接验证，因此在检查结果时，应着重检查所设计的解决问题的方案是否完备，有无重复或遗漏，也可采用多种不同的方法求解，看看是否相同.在对排列组合问题分类时，分类标准应统一，否则易出现遗漏或重复.二、基础训练1.（04福建）某校高二年级共有六个班级，现从外地转入4名学生，要安排到该年级的两个班级且每班安排2名，则不同的安排方案种数为A. A26C24B.21A26C24C. A26A24D.2A262.从5名学生中选出4名分别参加数学、物理、化学、外语竞赛，其中A不参加物理、化学竞赛，则不同的参赛方案种数为A.24B.48C.120D.723. 5本不同的书，全部分给四个学生，每个学生至少1本，不同分法的种数为A.480B.240C.120D.964.从1，3，5，7中任取2个数字，从0，2，4，6，8中任取2个数字组成没有重复数字的四位数，其中能被5整除的四位数共有_____________个.（用数字作答）5.市内某公共汽车站有10个候车位（成一排），现有4名乘客随便坐在某个座位上候车，则恰好有5个连续空座位的候车方式共有_____________种.（用数字作答）例1. 从6名短跑运动员中选4人参加4×100 m接力，如果其中甲不能跑第一棒，乙不能跑第四棒，问共有多少种参赛方法?例2. 对某种产品的6件不同正品和4件不同次品一一进行测试，至区分出所有次品为止.若所有次品恰好在第5次测试时被全部发现，则这样的测试方法有多少种可能?思考讨论用类似的方法，讨论如下问题.某种产品有5件不同的正品，4件不同的次品，现在一件件地进行检测，直到4件次品全部测出为止，则最后一件次品恰好在第6次检测时被测出，这样的检测方案有多少种？提示：问题相当于从10件产品中取出6件的一个排列，第6位为次品，前五位有其余3件次品，可分三步：先从4件产品中留出1件次品排第6位，有4种方法；再从5件正品中取2件，有C25种方法；再把3件次品和取出的2件正品排在前五位有A55种方法.所以检测方案种数为4×C25·A55=4800.例3. 在一块并排10垄的田地中，选择2垄分别种植A、B两种作物，每种作物种植一垄.为有利于作物生长，要求A、B两种作物的间隔不小于6垄，则不同的种植方法共有多少种？例4. 有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是A.234B.346C.350D.363例5. （1）一条长椅上有9个座位，3个人坐，若相邻2人之间至少有2个空椅子，共有几种不同的坐法?（2）一条长椅上有7个座位，4个人坐，要求3个空位中，恰有2个空位相邻，共有多少种不同的坐法?例6. 已知1<m<n，m，n∈N*，求证：（1+m）n>（1+n）m.四、同步练习 g3.1092 排列与组合的综合问题1.从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植.不同的种植方法共有A.24种B.18种C.12种D.6种2.四个不同的小球全部随意放入三个不同的盒子中，使每个盒子都不空的放法种数为A.A13A34B.C24A33C.C34A22D.C14C34C223．（05湖北卷）把一同排6张座位编号为1，2，3，4，5，6的电影票全部分给4个人，每人至少分1张，至多分2张，且这两张票具有连续的编号，那么不同的分法种数A．168 B．96 C．72 D．1444.（05江苏卷）四棱锥的8条棱代表8种不同的化工产品,有公共点的两条棱代表的化工产品放在同一仓库是危险的,没有公共顶点的两条棱多代表的化工产品放在同一仓库是安全的,现打算用编号为①、②、③、④的4个仓库存放这8种化工产品,那么安全存放的不同方法种数为（A）96 （B）48 （C）24（D ）05．从6名短跑运动员中选出4人参加4 × 100米接力赛，如果甲、乙两人都不跑第一棒，那么不同的参赛方案有 A ．180种 B ．240种 C ．300种 D ．360种6.书架上原有5本书，再放上2本，但要求原有书的相对顺序不变，则不同的放法有_____________种.7.（04浙江）设坐标平面内有一个质点从原点出发，沿x 轴跳动，每次向正方向或负方向跳1个单位，经过5次跳动质点落在点（3，0）（允许重复过此点．．）处，则质点不同的运动方法共有__________种.（用数字作答）8.在一张节目表上原有6个节目，如果保持这些节目的相对顺序不变，再添加进去三个节目，求共有多少种安排方法? 9. 18人的旅游团要选一男一女参加生活服务工作，有两位老年男人不在推选之列，共有64种不同选法，问这个团中男女各几人?10. 如下图，矩形的对角线把矩形分成A 、B 、C 、D 四部分，现用五种不同色彩给四部分涂色，每部分涂1种颜色，要求共边的两部分颜色互异，共有多少种不同的涂色方法?A BCD11. 6名运动员分到4所学校去做教练，每校至少1人，有多少种不同的分配方法?参与答案基本训练1. 将4名学生均分成两组，方法数为21C 24，再分配给6个年级中的2个，分配方法数为A 26，∴合要求的安排方法数为21C 24·A 26.答案：B2.若不含A ，则有A 44种；若含有A ，则有C 34·C 12·A 33种.∴A44+C34·C12·A33=72.答案：D3.先把5本书中的两本捆起来（C25），再分成四份（A44），∴分法种数为C25·A44=240.答案：B4.①四位数中包含5和0的情况：C13·C14·（A33+A12·A22）=120.②四位数中包含5，不含0的情况：C13·C24·A33=108.③四位数中包含0，不含5的情况：C23C14A33=72.综上，四位数总数为120+108+72=300.答案：3005.把四位乘客当作4个元素作全排列有A44种排法，将一个空位和余下的4个空位作为一个元素插空有A25种排法.∴A44·A25=480.答案：480例题分析例1.解法一：问题分成三类：（1）甲、乙两人均不参加，有A44种；（2）甲、乙两人有且仅有一人参加，有2C34（A44－A33）种；（3）甲、乙两人均参加，有C24（A44－2A33＋A22）种.故共有252种.解法二：六人中取四人参加的种数为A46，除去甲、乙两人中至少有一人不排在恰当位置的有C12 A35种，因前后把甲、乙两人都不在恰当位置的种数A24减去了两次.故共有A46－C12A35＋A24=252种.评述：对于带有限制条件的排列、组合综合题，一般用分类讨论或间接法两种方法处理.例2.解：C14（C16C33）A44=576，第5次必测出一次品，余下3件在前4次被测出，从4件中确定最后一件品有C14种方法，前4次中应有1正品、3次品，有C16C33种，前4次测试中的顺序有A44种，由分步计数原理即得.评述：本题涉及一类重要问题，即问题中既有元素的限制，又有排列的问题，一般是先选元素（即组合）后排列.例3.解：依题意，A、B两种作物的间隔至少6垄，至多8垄.（1）间隔6垄时，有3×A22种；（2）间隔7垄时，有2×A22种.（3）间隔8垄时，有A22种.所以共有3A22+2A22+A22=12种种植方法.例4.解法一：分类讨论法.（1）前排一个，后排一个，2C18·C112=192.（2）后排坐两个（不相邻），2（10+9+8+…+1）=110.（3）前排坐两个，2·（6+5+…+1）+2=44个.∴总共有192+110+44=346个.解法二：考虑中间三个位置不坐，4号座位与8号座位不算相邻.∴总共有A219+2+2=346个.答案：B评述：本题考查分类讨论在解排列组合应用题中的运用.这是一道难度较大的小综合题.例5.解：（1）先将3人（用×表示）与4张空椅子（用□表示）排列如图（×□□×□□×），这时共占据了7张椅子，还有2张空椅子，一是分开插入，如图中箭头所示（↓×□↓□×□↓□×↓），从4个空当中选2个插入，有C24种插法；二是2张同时插入，有C14种插法，再考虑3人可交换有A33种方法.所以，共有A33（C24+C14）=60（种）.下面再看另一种构造方法：先将3人与2张空椅子排成一排，从5个位置中选出3个位置排人，另2个位置排空椅子，有A35C22种排法，再将4张空椅子中的每两张插入每两人之间，只有1种插法，所以所求的坐法数为A35·C22=60.（2）可先让4人坐在4个位置上，有A44种排法，再让2个“元素”（一个是两个作为一个整体的空位，另一个是单独的空位）插入4个人形成的5个“空当”之间，有A25种插法，所以所求的坐法数为A44·A25=480.例6.证法一：由二项式定理（1+m ）n =C 0n m 0+C 1n m 1+…+C nn m n，（1+n ）m =C 0m n 0+C 1m n 1+…+C mm m n ，又因为Ciinm =!A i i m in ，Ci i m n=!A i n i i m ，而A i n m i>A i i m n ，所以C 2n m 2>C 22n m ，C 33m n >C 3m n 3，…，C m m n m >C mm m n .又因为C 00m n =C 00n m ，C 11m n =C 11n m ，所以（1+m ）n >（1+n ）m.证法二：（1+m ）n >（1+n ）m⇔nln （1+m ）>mln （1+n ） ⇔mm )1ln(+>nn )1ln(+. 令f （x ）=xx )1ln(+，x ∈［2，+∞］，只要证f （x ）在［2，+∞］上单调递减，只要证f ′（x ）<0.f ′（x ）=2)1ln(])1[ln(x x x x x +⋅'-'+=)1()1ln(2)1(x x x x x ++-+.当x ≥2时，x －lg （1+x ）)1(x +<0，x 2（1+x ）>0，得f ′（x ）<0，即x ∈［2,+∞］时，f ′（x ）<0.以上各步都可逆推，得（1+m ）n >（1+n ）m.作业：1—4 BBDBB 6. 42 7. 58. 解法一：添加的三个节目有三类办法排进去：①三个节目连排，有C 17A 33种方法；②三个节目互不相邻，有A 37种方法；③有且仅有两个节目连排，有C 13C 17C 16A 22种方法.根据分类计数原理共有C 17A 33+A 37+C 13C 17C 16A 22=504种.解法二：从结果考虑，排好的节目表中有9个位置，先排入三个添加节目有A 39种方法，余下的六个位置上按6个节目的原有顺序排入只有一种方法.故所求排法为A 39=504种.解法三：6699A A =504.评述：插空法是处理排列、组合问题常用的方法.9.解：设这个团中有男人x 人，则有女人18－x 人，根据题意得C12-x · C118x-=64.解得x=10.∴这个团中有男10人，女8人.10.解法一：依题意，给四部分涂色，至少要用两种颜色，故可分成三类涂色：第一类，用4种颜色涂色，有A45种方法；第二类，用3种颜色涂色，选3种颜色的方法有C35种；在涂的过程中，选对顶的两部分（A、C或B、D）涂同色，另两部分涂异色有C12种选法；3种颜色涂上去有A33种涂法.共C35·C12·A33种涂法；第三类，用两种颜色涂色.选颜色有C25种选法；A、C与B、D各涂一色有A22种涂法.共C25·A22种涂法.所以共有涂色方法A45+C35·C12·A33+C25·A22=260种.解法二：区域A有5种涂色法；区域B有4种涂色法；区域C的涂色法有2类：若C与A涂同色，区域D有4种涂色法；若C与A涂不同色，此时区域C有3种涂色法，区域D也有3种涂色法.所以共有5×4×4+5×4×3×3=260种涂色法.11.解法一：先取人，后取位子.1，1，1，3：6人中先取3人有C36种取法，与剩余3人分到4所学校去有A44种不同分法，∴共C36A44种分法；1，1，2，2：6人中取2人、2人、1人、1人的取法有C26·C24·C12种，然后分到4所学校去，有222244AAA⋅种不同的分法，共C26·C24·C12·222244AAA⋅种分法.所以符合条件的分配方法有C36A44+C26·C24·C12·222244AAA⋅=1560种.解法二：先取位子，后取人.1，1，1，3：取一个位子放3个人，有C14种取法，6人中分别取3人、1人、1人、1人的取法有C36·C13·C12·C11种，∴共有C14·C36·C13·C12·C11种.1，1，2，2：先取2个位子放2（其余2个位子放1）有C24种取法，6人中分别取2人，2人，1人，1人的取法有C26·C24·C12·C11种，共有C24·C26·C24·C12·C11种.所以符合条件的分配方法有C14·C36·C13·C12+C24·C26·C24·C12=1560种.。

王进明 初等数论 习题及作业解答1．已知两整数相除，得商12，余数26，又知被除数、除数、商及余数之和为454．求被除数.解：1226,1226454,a b a b =++++=12261226454,b b ++++=(121)454122626390,b +=---=b =30, 被除数a =12b +26=360+26=386. 这题的后面部分是小学数学的典型问题之一——“和倍” 问题。

2．证明：(1) 当n ∈Z 且39(09)n q r r =+≤<时，r 只可能是0,1,8;证：把n 按被9除的余数分类，即：若n=3k, k ∈Z ，则3327n k =, r=0；若n=3k +1, k ∈Z ，则3322(3)3(3)3(3)19(331)1n k k k k k k =+++=+++,r=1； 若n=3k －1, k ∈Z ，则33232(3)3(3)3(3)19(331)8n k k k k k k =-+-=-+-+,r=8. (2) 当 n ∈Z 时，32326n n n -+的值是整数。

证 因为32326n n n -+=32236n n n -+，只需证明分子3223n n n -+是6的倍数。

32223(231)(1)(21)n n n n n n n n n -+=-+=--(1)(21)n n n n =--++=(1)(2)n n n --+(1)(1)n n n -+.由k ! 必整除k 个连续整数知：6 |(1)(2)n n n --,6 |(1)(1)n n n -+.或证：2!|(1)n n -, (1)n n -必为偶数.故只需证3|(1)(21)n n n --.若3|n, 显然3|(1)(21)n n n --；若n 为3k +1, k ∈Z ，则n －1是3的倍数，得知(1)(21)n n n --为3的倍数；若n 为3k －1, k ∈Z ，则2n －1=2(3k －1)－1=6k-3, 2n －1是3的倍数.综上所述，(1)(21)n n n --必是6的倍数,故命题得证。

第一章 整数的可除性§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 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)(2n n n n n n n ++=+++-(1)(2)(1)(1n 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 ++==-=-，则有 1102222b b q q t a bs a b a b t ++-≤=-=-=-<∴≤若0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证． 下证唯一性而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,ss 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 rq r -=，┄,d '|21(,)n n n n r r q r a b --=+=, 即d '是(,)a b 的因数。