第十讲第十讲数论中的计数知识站牌六年级秋季六年级秋季进位制数论中的规律六年级暑期数论中的计数六年级暑期五年级春季数论中的最值位值原理数论中的范围中符合条件的个数的多少漫画释义第11级上优秀A版教师版1\n课堂引入p1.2300年前，古希腊数学家欧几里得就已证明素数有无穷多个，并提出一些素数可写成“2-1”的形式，这里的指数p也是一个素数.这种特殊形式的素数具有独特的性质和无穷的魅力，千百年来一直吸引着包括数学大师费马、笛卡尔、哥德巴赫、欧拉、高斯、哈代在内的众多数学家.17p世纪法国数学家、法兰西科学院奠基人马林•梅森是其中成果较为卓著的一位，因此后人将“2-1”型的素数称为“梅森素数”.312.1772年，有“数学英雄”美名的瑞士数学大师欧拉在双目失明的情况下，靠心算证明了2-1(即2147483647)是第8个梅森素数.在“手算笔录”的年代，人们历尽艰辛，仅找到12个梅森素数.幸而计算机的发明加速了梅森素数的探究进程.1952年，美国数学家拉婓尔•鲁滨逊等人使用52160712792203SWAC型计算机在短短的几个月内，就找到了5个梅森素数：2-1、2-1、2-1、2-1和22812-1.3.1996年初，美国数学家和程序设计师乔治•沃特曼编制了一个梅森素数计算程序，并把它放在网页上供数学家和业余数学爱好者免费使用，这就是著名的“互联网梅森素数大搜索”(GIMPS)项目.该项目利用大量普通计算机的闲置处理能力来获得相当于超级计算机的运算能力.这一项目还有一段有趣的插曲：美国一家电话公司的雇员麦克•福雷斯特偷偷地使用公司内的2585台计算机参加GIMPS项目，随后公司发现计算机经常会出些差错，本来只需要5秒钟就可以接通的电话号码，需要5分钟才能接通.联邦调查局最终查到了原因，福雷斯特承认“被GIMPS项目引诱”．他最后被解雇，并被罚款一万美元.由此看来，梅森素数的吸引力足以使人疯狂.4.梅森素数是否有无穷多个？这是目前尚未解决的著名数学谜题.迄今为止，人类仅发现47个梅森素数.这种素数珍奇而迷人，它在促进计算技术、密码技术、程序设计技术的发展中有着巨大作用.教学目标1.复习数论模块和计数模块的相关知识，如整除性质、加乘原理、排列组合等.2.灵活使用以上知识解决数论中的计数综合问题.3.复习容斥原理，尤其是在应用问题中的使用.2第11级上优秀A版教师版\n第十讲经典精讲1.常见数字的整除判定方法1)一个数的末位能被2或5整除，这个数就能被2或5整除；2)一个数各个数位上数字之和能被3或9整除，这个数就能被3或9整除；3)如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整除.2.加法原理一般地，如果完成一件事有k类方法，第一类方法中有m1种不同做法，第二类方法中有m2种不同做法，…，第k类方法中有m种不同做法，则完成这件事共有Nmm……m种不同方k12k法，这就是加法原理．可以简记为：“加法分类，类类独立”．3.乘法原理完成一件事，这个事情可以分成n个必不可少的步骤，第1步有A种不同的方法，第二步有B种不同的方法，……，第n步有N种不同的方法．那么完成这件事情一共有A×B×……×N种不同的方法．这就是乘法原理．4.容斥原理ABABABABCABCABBCACABC知识回顾1.写出50以内的所有质数.【分析】2,3,5,7,11,13,17,19,23,29,31,37,41,43,472.写出24的所有因数【分析】1,24,2,12,3,8,4,63.（12,18）=；[20,30]=.【分析】6；604.两个质数之和为39，求这两个质数的乘积是多少.【分析】因为和为奇数，所以这两个数必为一奇一偶，所以其中一个是2，另一个是37，乘积为74.5.写出全部除109后余数为4的两位数．【分析】1094105357．因此，这样的两位数是：15；35；21．第11级上优秀A版教师版3\n例题思路例1：乘法原理、排列、整除性质例2：缩小包围圈例例3：同余类例例4：容斥原理例例5：容斥原理应用题例例1用1、2、3、4、5、6可以组成多少个没有重复数字的是5的倍数的三位数？（学案对应：学案1）【分析】个位数字已知，问题变成从从5个元素中取2个元素的排列问题，已知n5，m2，根2据排列数公式，一共可以组成P5420(个)符合题意的三位数．5【想想练练】将下图中20张扑克牌分成10对，每对红心和黑桃各一张.问：你能分出几对这样的牌，两张牌上的数的乘积除以10的余数是1?(将A看成1)【分析】本题实际上是求1到10这些数中，取出2个数（可以重复）相乘，能组成几个个位是1的数.显然，双数不成.所以只能是1×1，3×7，7×3和9×9，共4对.例2三位数中，能被5和7同时整除的数共有多少个？（学案对应：学案2）【分析】[5,7]=35,1000÷35=28……20,100÷35=2……30所以符合要求的最小三位数是35×3，最大三位数是35×28，合共28-3+1=26（个）【想想练练】三位数中，被6和7除余数都是5的数共有多少个？【分析】假设这个三位数是a，根据题意，a5能被6和7整除，即a5为42的倍数，因为10042216,1000422334，所以a5最小为423，最大为4223，满足题意的数共有233121个4第11级上优秀A版教师版\n第十讲费马素数法国数学家费马（1601—1665）是数学史上一位传奇人物.费马的主要职业是律师，数学仅是他的业余爱好.费马被誉为“数论之父”，他有着了不起的直观天才，一生中提出过很多数学猜想.令人惊奇的是，他的几乎所有猜想全被后人一一证实，仅有一个例外.那就是他猜想：凡是形如mn21（其中m2）的数，都是素数（质数），后人称为费马素数.n2如果将n0,1,2,3,4代入21，得到的数确实都是质数：3,5,17,257,65537.可是对n5，在321738年，欧拉惊人地发现有分解式：2142949672976416700417.这说明费马的猜想错了！谁知欧拉的这一分解式，竟是“一石激起千层浪”！从此以后，人们再也没有找2n到第六个费马素数，相反地，倒是已经找到了46个形如21的数不是素数.于是人们又猜测，费马素数仅有上述5个，但也无法证明.这是数学史上的又一个悬案！例3从1～9这9个数码中取出3个，使它们的和是3的倍数，则不同取法有_______种.（学案对应：学案3）【分析】（1）3个数都是3的倍数，有1种情况（2）3个数除以3都余1，有1种情况（3）3个数除以3都余2，有1种情况（4）一个除以3余1，一个除以3余2，一个是3的倍数，有：3×3×3=27种情况,所以，一共有1+1+1+27=30种不同取法.例4在从1至100的自然数中，既不能被5整除，又不能被7整除的数有多少个?【分析】1～100之间，5的倍数有100÷5=20个，7的倍数有100÷7=14.2即14个，因为既是5的倍数，又是7的倍数的数一定是35的倍数，所以这样的数有35和70两个．所以既不能被5整除，又不能被7整除的数有100-20-14+2=68个．【想想练练】在一根长木棍上，有三种刻度线，第一种刻度线将木棍分成十等份；第二种将木棍分成十二等份；第三种将木棍分成十五等份；如果沿每条刻度线将木棍锯断，则木棍总共被锯成________段．【分析】假设木棍长60cm，则沿第一种刻度线锯成的木棍每段长60106cm，沿第二种刻度线锯成的木棍每段长60125cm，沿第三种刻度线锯成的木棍每段长60144cm．因为，沿三种刻度线可将木棍分别锯成10、12、15段；沿第一、二种重合的刻度线可将木棍锯成60[6,5]2段，沿第一、三种重合的刻度线可将木棍锯成60[6,4]5段，沿第二、三种重合的刻度线可将木棍锯成60[5,4]3段；沿三种刻度重合的刻度线可将木棍锯成第11级上优秀A版教师版5\n60[6,5,4]1段．应该减去重复计算的沿任意两种重合的刻度线锯成的段数，应加上多减去的沿三种刻度重合的刻度线锯成的段数．所以，沿每条刻度线将木棍锯断，则木棍总共被锯成101215253128段．例5有2000盏亮着的电灯，各有一个拉线开关控制着，现按其顺序编号为1，2，3，…，2000，然后将编号为2的倍数的灯线拉一下，再将编号为3的倍数的灯线拉一下，最后将编号为5的倍数的灯线拉一下，三次拉完后，亮着的灯有多少盏？（学案对应：学案4）ADB2G3EFC5【分析】三次拉完后，亮着的灯包括不是2、3、5的倍数的数以及是6、10、15的倍数但不是30的倍数的数．1～2000这2000个正整数中，2的倍数有1000个，3的倍数有666个，5的倍数有400个，6的倍数有333个，10的倍数有200个，15的倍数有133个，30的倍数有66个，亮着的灯一共有2000-1000-666-400+2×（333+200+133）-4×66=1002盏．找朋友教师先为班上的每个学生编上学号（例如从1到20），然后让同学们在大卡片上写上自己的学号，再贴在背上.游戏开始的时候，20名同学围成一圈，等待老师宣布“找朋友”的要求.例如，老师说：“现在找一个朋友，使你们的数字之和除以5的余数是2！”然后，老师限定学生在10秒钟内找到自己的朋友，时间一到必须停止行动.由于满足要求的“朋友”不止一个，所以可以进行几轮游戏，看谁找到的“朋友”最多.这个游戏既考验学生的数论计数能力，又考验他们的行动灵敏性.老师还可以加大游戏的难度，例如要求3个数之和能被11整除，这样每轮游戏中必定有人因为落空而被淘汰.6第11级上优秀A版教师版\n第十讲杯赛提高从101到900这800个自然数中，数字和被8整除的数共有______个.【分析】数字和被8整除，则数字和可能为8、16、24①数字和8=8+0+0=7+1+0=6+2+0=5+3+0=4+4+0=6+1+1=5+2+1=4+3+1=4+2+2=3+3+2这样的数共有13222332636个②数字和16=9+7+0=8+8+0=9+6+1=9+5+2=9+4+3=8+7+1=8+6+2=8+5+3=8+4+4=……这样的数共有58个③数字和=24=9+9+6=9+8+7=8+8+8这样的数共有6个所以满足题意的数字共有100个附加题1.一根101厘米长的木棒，从同一端开始，第一次每隔2厘米画一个刻度，第二次每隔3厘米画一个刻度，第三次每隔5厘米画一个刻度，如果按刻度把木棒截断，那么可以截出多少段．【分析】要求出截出的段数，应当先求出木棒上的刻度数，而木棒上的刻度数，相当于1、2、3、…、100、101这101个自然数中2或3或5的倍数的个数，为：10110110110110110110174，故木棒上共有74个刻度，235232535235可以截出75段．2.1到60这60个自然数中，选取两个数，使它们的乘积是被5除余2的偶数，问，一共有多少种选法？【分析】两个数的乘积被5除余2有两类情况，一类是两个数被5除分别余1和2，另一类是两个数被5除分别余3和4，只要两个乘数中有一个是偶数就能使乘积也为偶数.1到60这60个自然数中，被5除余1、2、3、4的偶数各有6个，被5除余1、2、3、4的奇数也各有6个，所以符合条件的选取方式一共有（66666666）（6666）216种．3.从1到999这999个自然数中有个数的各位数字之和能被4整除．【分析】由于在一个数的前面写上几个0不影响这个数的各位数字之和，所以可以将1到999中的一位数和两位数的前面补上两个或一个0，使之成为一个三位数．现在相当于要求001到999中各位数字之和能被4整除的数的个数．一个数除以4的余数可能为0，1，2，3，0～9中除以4余0的数有3个，除以4余1的也有3个，除以4余2和3的各有2个．三个数的和要能被4整除，必须要求它们除以4的余数的和能被4整除，余数的情况有如下5种：000；013；022；112；233．⑴如果是000，即3个数除以4的余数都是0，则每位上都有3种选择，共有33327种可能，但是注意到其中也包含了000这个数，应予排除，所以此时共有27126个；第11级上优秀A版教师版7\n⑵如果是013，即3个数除以4的余数分别为0，1，3，而在3个位置上的排列有3!6种，所以此时有3326108个；⑶如果是022，即3个数除以4的余数分别为0，2，2，在3个位置上的排列有3种，所以此时有322336个；⑷如果是112，即3个数除以4的余数分别为1，1，2，在3个位置上的排列有3种，所以此时有332354个；⑸如果是233，即3个数除以4的余数分别为2，3，3，在3个位置上的排列有3种，此时有222324个．根据加法原理，共有26108365424248．4.以105为分母的最简真分数共有多少个？它们的和为多少？【分析】以105为分母的最简真分数的分子与105互质，105=3×5×7，所以也是求1到105不是3、5、7倍数的数有多少个，3的倍数有35个，5的倍数有21个，7的倍数有15个，15的倍数有7个，21的倍数有5个，35的倍数有3个，105的倍数有1个，所以105以内与105互质的数有105-35-21-15+7+5+3-1=48个，显然如果n与105互质，那么（105-n）与n互质，所以以105为分母的48个最简真分数可两个两个凑成1，所以它们的和为24.5.分子小于6，分母小于60的最简真分数共有多少个？【分析】分类枚举：根据分子是1,2,3,4,5这5种情况进行讨论．分子是1：分母取2到59，所以共有58个；分子是2：分母取小于60大于2的奇数，所以共有30129个；分子是3：分母不能是3的倍数，由于60320,602040（60本身是3的倍数），再排除分母是1或2，共有40238个；分子是4：分母取小于60大于4的奇数，共有28个；分子是5：分母不能是5的倍数，由于60512,601248（60本身是5的倍数），再排除分母是1、2、3或4，还剩48444个.综上所述，满足条件的分数共有5829382844197个．6.大明、中明与小明是三兄弟，年龄依次从大到小．已知大明岁数与小明岁数的最小公倍数是15，中明岁数与小明岁数的最小公倍数是12，那么他们兄弟三人的总岁数共有几种情况？2【分析】因为1535,1232，可见小明的岁数只有1或3两种情况．如果小明的岁数是1，那么大明的岁数是15，中明的岁数是12．如果小明的岁数是3，那么中明的岁数是4或12，大明的岁数是5或15．若中明的岁数是4，大明的岁数可以是5或15；若中明的岁数是12，大明的岁数只能是15．那么，三人的总岁数共有以下4种情况：1121528，34512，341522，3121530.7.如果某整数同时具备如下3条性质：①这个数与1的差是质数，②这个数除以2所得的商也是质数，③这个数除以9所得的余数是5．那么我们称这个整数为幸运数．请问两位幸运数共有多少个？【分析】由①可知两位幸运数不可能是奇数，否则它与1的差能被2整除；由②可知两位幸运数不可8第11级上优秀A版教师版\n第十讲能是4的倍数，否则这个数除以2所得的商是2的倍数；再结合③，易得两位幸运数为只有14．答案是1个．知识点总结1.1）一个数的末位能被2或5整除，这个数就能被2或5整除；2）一个数各个数位上数字之和能被3或9整除，这个数就能被3或9整除；3）如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整除.2.加法原理：“加法分类，类类独立”．3.乘法原理：完成一件事可以分成n个必不可少的步骤，第1步有A种不同的方法，第二步有B种不同的方法，……，第n步有N种不同的方法．那么完成这件事情一共有A×B×…×N种不同的方法．4.ABABABABCABCABBCACABC家庭作业1.有五张卡，分别写有数字1、2、4、5、8．现从中取出3张卡片，并排放在一起，组成一个三位数，问：可以组成多少个不同的偶数？【分析】分三步取出卡片．首先因为组成的三位数是偶数，个位数字只能是偶数，所以先选取最右边的也就是个位数位置上的卡片，有2、4、8三种不同的选择；第二步在其余的4张卡片中任取一张，放在最左边的位置上，也就是百位数的位置上，有4种不同的选法；最后从剩下的3张卡片中选取一张，放在中间十位数的位置上，有3种不同的选择．根据乘法原理，可以组成3×4×3=36个不同的三位偶数．2..恰好能被6,7,8整除的四位数有多少个？【分析】由于6,7,8的最小公倍数为168,10001685160,100001685988，所以能被6,7,8整除的最小四位数为1686，最大四位数为16859，共有596154个3.从1,2,3,4,5,6中选取若干个数，使得它们的和是3的倍数，但不是5的倍数．那么共有种不同的选取方法．【分析】从16这些数中选取的数的和小于等于21，满足条件的和数有3、6、9、12、18、21分别有2、4、5、5、2、1种选取方法，共24552119种选取方法．第11级上优秀A版教师版9\n4.在1~100的全部自然数中，不是3的倍数也不是5的倍数的数有多少个？AB【分析】如图，用长方形表示1~100的全部自然数，A圆表示1~100中3的倍数，B圆表示1~100中5的倍数，长方形内两圆外的部分表示既不是3的倍数也不是5的倍数的数．由1003331可知，1~100中3的倍数有33个；由100520可知，1~100中5的倍数有20个；由100（35）610可知，1~100既是3的倍数又是5的倍数的数有6个．由包含排除法，3或5的倍数有：3320647(个)．从而不是3的倍数也不是5的倍数的数有1004753(个)．5.40名同学编号由1到40，面向老师排成一排，老师第一次让编号是2的倍数的同学向后转，第二次让编号是3的倍数的同学向后转，请问现在有多少名同学面向老师？404040【分析】2的倍数有=20个，3的倍数有=13个，6的倍数有=6个，那么能被2整除236但不能被3整除的数有20-6=14个，能被3整除但不能被2整除的数有13-6=7（个），所以向后转了一次的同学有14+7=21（个），余下40-21=19（个）同学面向老师．6.有两个不完全一样的正方体，每个正方体的六个面上分别标有数字1、2、3、4、5、6．将两个正方体放到桌面上，向上的一面数字之和为偶数的有多少种情形？【分析】要使两个数字之和为偶数，只要这两个数字的奇偶性相同，即这两个数字要么同为奇数，要么同为偶数，所以，要分两大类来考虑．第一类，两个数字同为奇数．由于放两个正方体可认为是一个一个地放．放第一个正方体时，出现奇数有三种可能，即1，3，5；放第二个正方体，出现奇数也有三种可能，由乘法原理，这时共有339种不同的情形．第二类，两个数字同为偶数，类似第一类的讨论方法，也有339种不同情形．最后再由加法原理即可求解．两个正方体向上的一面数字之和为偶数的共有333318种不同的情形．A版学案【学案1】用2,0,1,3这四个数字能排成多少个能被11整除的四位数？【分析】根据11的整除特征，把四位数的各个数位分成奇数位与偶数位，又因为2130，所以数字0,3要么同时放在奇数位，要么同时放在偶数位，对于前一种情况，可排出1023,1320,2013,2310四个符合条件的四位数，对于后一种情况，可排出3102,3201两个符合条件的数，所以一共有426（个）．【学案2】在大于2004的整数中，找出所有被47除后商与余数相等的数，这些数共有_________个.【分析】根据题意，设这样的数被47除后商和余数都是a（(a47)，这个数可表示为47aa48a，因此48a2004，易得a至少为42，所以满足题意的数共有464215（个）10第11级上优秀A版教师版\n第十讲【学案3】从1到20中，最多能取______个数，使任意两个数不是3倍关系.【分析】1和3共存，2和6不能共存，3和9不能共存，4和12不能共存，5和15不能共存，6和18不能共存.要破坏这些组合，至少要去掉4个数，例如3,4,5,6.【学案4】写有1到100编号的灯100盏，亮着排成一排，第一次把编号是3的倍数的灯拉一次开关，第二次把编号是5的倍数的灯拉一次开关，那么亮着的灯还有多少盏？【分析】因为灯在开始的时候是亮着的，所以拉了两次或者没拉的灯最后还是亮的．没拉的灯有100100100100100()100(33206)53(盏)，拉两次的有6(盏)，最353535后亮着的灯一共为53659(盏).第11级上优秀A版教师版11