数论模块(教师版)

教师：教师：学生：上课时间：2013年月日:-:上课地点：校区上课进度：第讲数论模块综合复习知识框架知识框架一．质数与合数1．根本概念一个数除了1和它本身，不再有别的约数，这个数叫做质数(也叫做素数).一个数除了1和它本身，还有别的约数，这个数叫做合数.要特别记住：0和1不是质数，也不是合数.考点：⑴值得注意的是很多题都会以质数2的特殊性为考点.⑵除了2和5，其余质数个位数字只能是1，3，7或9.这也是很多题解题思路，需要大家注意.；；；；；；；；.3.判断一个数是否为质数的方法根据定义如果能够找到一个小于p的质数q(均为整数)，使得q能够整除p，那么p就不是质数，所以我们只要拿所有小于p的质数去除p就可以了；但是这样的计算量很大，对于不太大的p，我们可以先找一个大于且接近p的平方数，再列出所有不大于K的质数，用这些质数去除p，如没有能够除尽的那么p就为质数.例如：149很接近，根据整除的性质149不能被2、3、5、7、11整除，所以149是质数.二、约数与倍数1．1求最大公约数的方法①分解质因数法：先分解质因数，然后把相同的因数连乘起来．例如：，，所以；②短除法：先找出所有共有的约数，然后相乘．例如：，所以；③辗转相除法：每一次都用除数和余数相除，能够整除的那个余数，就是所求的最大公约数．用辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个余数去除前一个余数，直到余数是0为止．那么，最后一个除数就是所求的最大公约数．(如果最后的除数是1，那么原来的两个数是互质的)．例如，求600和1515的最大公约数：；；；；；所以1515和600的最大公约数是15．求一组分数的最大公约数先把带分数化成假分数，其他分数不变；求出各个分数的分母的最小公倍数a；求出各个分数的分子的最大公约数b；即为所求．求最小公倍数的方法①分解质因数的方法；例如：，，所以；②短除法求最小公倍数；例如：，所以；③．先将各个分数化为假分数；求出各个分数分子的最小公倍数；求出各个分数分母的最大公约数；即为所求．例如：注意：两个最简分数的最大公约数不能是整数，最小公倍数可以是整数.例如：3.1求任一整数约数的个数一个整数的约数的个数是在对其严格分解质因数后，将每个质因数的指数(次数)加1后所得的乘积。如:1400严格分解质因数之后为，所以它的约数有(3+1)×(2+1)×(1+1)=4×3×2=24个。(包括1和1400本身)约数个数的计算公式是本讲的一个重点和难点，授课时应重点讲解，公式的推导过程是建立在开篇讲过的数字“唯一分解定理”形式根底之上，结合乘法原理推导出来的，不是很复杂，建议给学生推导并要求其掌握。难点在于公式的逆推，有相当一局部常考的偏难题型考察的就是对这个公式的逆用，即先告诉一个数有多少个约数，然后再结合其他几个条件将原数“复原构造”出来，或者是“构造出可能的最值”。3.2求任一整数的所有约数的和一个整数的所有约数的和是在对其严格分解质因数后，将它的每个质因数依次从1加至这个质因数的最高次幂求和，然后再将这些得到的和相乘，乘积便是这个合数的所有约数的和。如：，所以21000所有约数的和为此公式没有第一个公式常用，推导过程相对复杂，需要许多步提取公因式，建议帮助学生找规律性的记忆即可。三、余数问题三大余数定理：a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。例如：23，19除以5的余数分别是3和4，所以23+19=42除以5的余数等于3+4=7除以5的余数，即2.a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2.假设两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：a≡b(modm)，左边的式子叫做同余式。同余式读作：a同余于b，模m。由同余的性质，我们可以得到一个非常重要的推论：假设两个数a，b除以同一个数m得到的余数相同，那么a，b的差一定能被m整除用式子表示为：如果有a≡b(modm)，那么一定有a－b＝mk,k是整数，即m|(a－b)中国剩余定理一个自然数分别除以3，5，7后，得到三个余数分别为2，3，2.那么我们首先构造一个数字，使得这个数字除以3余1，并且还是5和7的公倍数。先由，即5和7的最小公倍数出发，先看35除以3余2，不符合要求，那么就继续看5和7的“下一个”倍数是否可以，很显然70除以3余1类似的，我们再构造一个除以5余1，同时又是3和7的公倍数的数字，显然21可以符合要求。最后再构造除以7余1，同时又是3，5公倍数的数字，45符合要求，那么所求的自然数可以这样计算：，其中k是从1开始的自然数。也就是说满足上述关系的数有无穷多，如果根据实际情况对数的范围加以限制，那么我们就能找到所求的数。例如对上面的问题加上限制条件“满足上面条件最小的自然数”，那么我们可以计算得到所求如果加上限制条件“满足上面条件最小的三位自然数”,我们只要对最小的23加上[3,5,7]即可，即23+105=128。四、位值原理位值原理的定义：同一个数字，由于它在所写的数里的位置不同，所表示的数值也不同。也就是说，每一个数字除了有自身的一个值外，还有一个“位置值”。例如“2”,写在个位上，就表示2个一，写在百位上，就表示2个百，这种数字和数位结合起来表示数的原那么，称为写数的位值原理。位值原理的表达形式：以六位数为例：a×100000+b×10000+c×1000+d×100+e×10+f。五、数的进制我们常用的进制为十进制，特点是“逢十进一”。在实际生活中，除了十进制计数法外，还有其他的大于1的自然数进位制。比方二进制，八进制，十六进制等。二进制：在计算机中，所采用的计数法是二进制，即“逢二进一”。因此，二进制中只用两个数字0和1。二进制的计数单位分别是1、21、22、23、……，二进制数也可以写做展开式的形式，例如100110在二进制中表示为：(100110)2=1×25+0×24+0×23+1×22+1×21+0×20。二进制的运算法那么：“满二进一”、“借一当二”，乘法口诀是：零零得零，一零得零，零一得零，一一得一。注意：对于任意自然数n,我们有n0=1。n进制：n进制的运算法那么是“逢n进一，借一当n”，n进制的四那么混合运算和十进制一样，先乘除，后加减；同级运算，先左后右；有括号时先计算括号内的。进制间的转换：如右图所示。十进制十进制二进制十六进制八进制六、完全平方数常用性质1.完全平方数的尾数只能是0，1，4，5，6，9。不可能是2，3，7，8。2.在两个连续正整数的平方数之间不存在完全平方数。3.完全平方数的约数个数是奇数，约数的个数为奇数的自然数是完全平方数。，那么p能被整除。1.任何偶数的平方一定能被4整除；任何奇数的平方被4〔或8〕除余1.即被4除余2或3的数一定不是完全平方数。2.一个完全平方数被3除的余数是0或1.即被3除余2的数一定不是完全平方数。3.自然数的平方末两位只有：00，01，21，41，61，81，04，24，44，64，84，25，09，29，49，69，89，16，36，56，76，96。4.完全平方数个位数字是奇数〔1，5，9〕时，其十位上的数字必为偶数。5.完全平方数个位数字是偶数〔0，4〕时，其十位上的数字必为偶数。6.完全平方数的个位数字为6时，其十位数字必为奇数。7.凡个位数字是5但末两位数字不是25的自然数不是完全平方数；末尾只有奇数个“0”的自然数不是完全平方数；个位数字为1，4，9而十位数字为奇数的自然数不是完全平方数。3.重点公式回忆：平方差公式：

例题精讲例题精讲两个质数之和为，求这两个质数的乘积是多少.因为和为奇数，所以这两个数必为一奇一偶，所以其中一个是，另一个是，乘积为.我们要善于抓住此类题的突破口。如果a，b均为质数，且，那么______.根据题意a,b中必然有一个偶质数2，，当时，，当时不符合题意，所以.【例2】三个质数的乘积恰好等于它们和的11倍，求这三个质数.设这三个质数分别是、、，满足，那么可知、、中必有一个为11，不妨记为，那么，整理得()()，又，对应的、或、或、(舍去)，所以这三个质数可能是2，11，13或3，7，11.三个质数的乘积恰好等于它们的和的7倍，求这三个质数．设这三个质数分别是、、，满足，那么可知、、中必有一个为7，不妨记为，那么，整理得，又，对应的2、9(舍去)或3、5，所以这三个质数可能是3，5，7现有三个自然数，它们的和是1111，这样的三个自然数的公约数中，最大的可以是多少？只知道三个自然数的和，不知道三个自然数具体是几，似乎无法求最大公约数．只能从唯一的条件“它们的和是1111”入手分析．三个数的和是1111，它们的公约数一定是1111的约数．因为，它的约数只能是1，11，101和1111，由于三个自然数的和是1111，所以三个自然数都小于1111，1111不可能是三个自然数的公约数，而101是可能的，比方取三个数为101，101和909．所以所求数是101．10个非零不同自然数的和是1001，那么它们的最大公约数的最大值是多少？设M为这10个非零不同自然数的最大公约数，那么这10个不同的自然数分别可以表示为：，其中那么根据题意有：因为10个不同非零自然数的和最小为55，所以M最大可以为13数360的约数有多少个?这些约数的和是多少?360分解质因数:360=2×2×2×3×3×5=××5；360的约数可以且只能是××,(其中a,b,c均是整数,且a为0～3,6为0～2,c为0～1)．因为a、b、c的取值是相互独立的,由计数问题的乘法原理知,约数的个数为(3+1)×(2+1)×(1+1)=24．我们先只改动关于质因数3的约数,可以是l,3,,它们的和为(1+3+),所以所有360约数的和为(1+3+)××；我们再来确定关于质因数2的约数,可以是l,2,,,它们的和为(1+2++)，所以所有360约数的和为(1+3+)×(1+2++)×5w；最后确定关于质因数5的约数,可以是1,5,它们的和为(1+5),所以所有360的约数的和为(1+3+)×(1+2++)×(1+5)．于是,我们计算出值:13×15×6=1170．所以,360所有约数的和为1170．两个数都是只含质因数3和5，它们的最大公约数是75，有12个约数，有10个约数，求与的和．因为，如果设，，那么中较小的数是1，中较小的数是2．由于一个数的约数的个数等于它分解质因数后每个质因数的次数加1的乘积．所以，．又，，由于，所以，那么，，得到，．那么，得到，所以，，．一个两位数有6个约数，且这个数最小的3个约数之和为10，那么此数为几？最小的三个约数中必然包括约数1，除去1以外另外两个约数之和为9，由于9是奇数，所以这两个约数的奇偶性一定是相反的，其中一定有一个是偶数，如果一个数包含偶约数，那么它一定是2的倍数，即2是它的约数。于是2是这个数第二小的约数，而第三小的约数是7，所以这个两位数是14的倍数，由于这个两位数的约数中不含3、4、5、6，所以这个数只能是14或98，其中有6个约数的是98．如果你写出12的所有约数，1和12除外，你会发现最大的约数是最小约数的3倍．现有一个整数n，除掉它的约数1和n外，剩下的约数中，最大约数是最小约数的15倍，那么满足条件的整数n有哪些？设整数n除掉约数1和n外，最小约数为a，可得最大约数为，那么．那么3、5、a都为n的约数．因为a是n的除掉约数1外的最小约数，那么．当时，；当时，．所以满足条件的整数n有60和135．在1到100中，恰好有6个约数的数有多少个？，故6只能表示为或，所以恰好有6个约数的数要么能表示成某个质数的5次方，要么表示为某个质数的平方再乘以另一个质数，100以内符合前者的只有32，符合后者的数枚举如下：所以符合条件的自然数一共有个．恰有8个约数的两位数有________个．根据约数个数公式，先将8进行分解：，所以恰有8个约数的数至多有3个不同的质因数，分解质因数后的形式可能为，，．其中由于，所以形式的没有符合条件的两位数；形式中，B不能超过3，即可能为2或3，有、、、、，共5个；形式的有、、、、，共5个．所以共有个符合条件的数．用某自然数去除，得到商是46，余数是，求和．因为是的倍还多,得到，得，所以，．【稳固】甲、乙两数的和是，甲数除以乙数商余，求甲、乙两数．(法1)因为甲乙，所以甲乙乙乙乙；那么乙，甲乙．(法2)将余数先去掉变成整除性问题，利用倍数关系来做：从中减掉以后，就应当是乙数的倍，所以得到乙数，甲数．一个自然数，除以11时所得到的商和余数是相等的，除以9时所得到的商是余数的3倍，这个自然数是_________.设这个自然数除以11余，除以9余，那么有，即，只有，，所以这个自然数为。【例3】有一个大于1的整数，除所得的余数相同，求这个数.这个题没有告诉我们，这三个数除以这个数的余数分别是多少，但是由于所得的余数相同，根据同余定理，我们可以得到：这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数．，，，的约数有，所以这个数可能为。有一个整数，除39,51,147所得的余数都是3，求这个数.【解析】(法1)，，，12的约数是，因为余数为3要小于除数，这个数是；(法2)由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数．，，，所以这个数是．【例4】一个三位数除以17和19都有余数，并且除以17后所得的商与余数的和等于它除以19后所得到的商与余数的和．那么这样的三位数中最大数是多少，最小数是多少？设这个三位数为，它除以17和19的商分别为和，余数分别为和，那么．根据题意可知，所以，即，得．所以是9的倍数，是8的倍数．此时，由知．由于为三位数，最小为100，最大为999，所以，而，所以，，得到，而是9的倍数，所以最小为9，最大为54．当时，，而，所以，故此时最大为；当时，，由于，所以此时最小为．所以这样的三位数中最大的是930，最小的是154．【例5】与的和除以7的余数是________．找规律．用7除2，，，，，，…的余数分别是2，4，1，2，4，1，2，4，1，…,2的个数是3的倍数时，用7除的余数为1；2的个数是3的倍数多1时，用7除的余数为2；2的个数是3的倍数多2时，用7除的余数为4．因为，所以除以7余4．又两个数的积除以7的余数，与两个数分别除以7所得余数的积相同．而2003除以7余1，所以除以7余1．故与的和除以7的余数是．【稳固】求的余数．因为，，，根据同余定理(三)，的余数等于的余数，而，，所以的余数为5．【例6】被除所得的余数是多少？31被13除所得的余数为5，当n取1，2，3，时被13除所得余数分别是5，12，8，1，5，12，8，1以4为周期循环出现，所以被13除的余数与被13除的余数相同，余12，那么除以13的余数为12；30被13除所得的余数是4，当n取1，2，3，时，被13除所得的余数分别是4，3，12，9，10，1，4，3，12，9，10，以6为周期循环出现，所以被13除所得的余数等于被13除所得的余数，即4，故除以13的余数为4；所以被13除所得的余数是．【例7】一个大于1的数去除290，235，200时，得余数分别为，，，那么这个自然数是多少？根据题意可知，这个自然数去除290，233，195时，得到相同的余数〔都为〕．既然余数相同，我们可以利用余数定理，可知其中任意两数的差除以这个数肯定余0．那么这个自然数是的约数，又是的约数，因此就是57和38的公约数,因为57和38的公约数只有19和1，而这个数大于1，所以这个自然数是19．【例1】某三位数和它的反序数的差被99除，商等于______与______的差；此题属于根底型题型。我们不妨设a＞b＞c。(-〕÷99=[(100a+10b+c)-(100c+10b+a)]÷99=(99a-99c)÷99=a-c；与的差被9除，商等于______与______的差；(-〕÷9=[(10a+b)-(10b+a)]÷9=(9a-9b)÷9=a-b；【例2】.原式：1111a＋111b＋11c＋d＝1370，所以a＝1，那么111b＋11c＋d＝1370－1111＝259，推知b＝2；进而推知c＝3，d=4所以=1234。一个四位数加上它的各位数字之和后等于2008，那么所有这样的四位数之和为多少．设这样的四位数为，那么，即，那么或2．⑴假设，那么，得，，；⑵假设，那么，由于，所以，所以，故为9，，那么为偶数，且，故，由为偶数知，，；所以，这样的四位数有2003和1985两个，其和为：．【例3】有一个两位数，如果把数码3加写在它的前面，那么可得到一个三位数，如果把数码3加写在它的后面，那么可得到一个三位数，如果在它前后各加写一个数码3，那么可得到一个四位数．将这两个三位数和一个四位数相加等于．求原来的两位数．设原来的两位数是，那么得到的两个三位数分别为和，四位数为，由题知，即，，故．如果把数码5加写在某自然数的右端，那么该数增加，这里A表示一个看不清的数码，求这个数和A。设这个数为x，那么10x+5-x=，化简得9x=，等号右边是9的倍数，试验可得A=1，x=1234。【例4】①________；②；③；④________；⑤假设，那么________．①对于这种进位制计算，一般先将其转化成我们熟悉的十进制，再将结果转化成相应的进制：；②可转化成十进制来计算：；如果对进制的知识较熟悉，可直接在二进制下对进行除法计算，只是每次借位都是2，可得；③此题涉及到3个不同的进位制，应统一到一个进制下．统一到十进制比拟适宜：；④十进制中，两个数的和是整十整百整千的话，我们称为“互补数”，凑出“互补数”的这种方法叫“凑整法”，在进制中也有“凑整法”，要凑的就是整．原式；⑤假设，那么，经试验可得．将二进制数(11010.11)2化为十进制数为多少？根据二进制与十进制之间的转化方法，(11010.11)2=1×24+1×23+0×22+1×21+0×20+1×2-1+1×2-2=16+8+0+2+0+0.5+0.25=26.75。此处老师在讲解的时候可以适当的拓宽，各种进制之间小数局部的转化方法。根据二进制与八进制之间的转化方法推导出二八对照表：八进制数01234567二进制数000001010011100101110111试求(2-1)除以992的余数是多少?我们通过左式的短除法，或者直接运用通过2次幂来表达为2进制：(992)=(1111100000)2，(2-1)2=我们知道在2进制中一定能整除 (1111100000)2，于是我们注意到，所以=因为能整除(1111100000)2，所以余数为(111111)2=2+24+23+22+21+1=63，所以原式的余数为63。计算除以26的余数．题中有3的次幂，令人联想到将题中的数转化成3进制下的数再进行计算．，而，所以，．由于整除，，所以余．所以除以26的余数为8．【附加思考题】设是质数，证明：，，…，被除所得的余数各不相同．【例1】是的平方．，，原式．下面是一个算式：，这个算式的得数能否是某个数的平方？判断一个数是否是某个数的平方，首先要观察它的个位数是多少．平方数的个位数只能是0，1，4，5，6，9，而2，3，7，8不可能是平方数的个位数．这个算式的前二项之和为3，中间二项之和的个位数为0，后面二项中每项都有因子2和5，个位数一定是0，因此，这个0算式得数的个位数是3，不可能是某个数的平方．【例2】1016与正整数a的乘积是一个完全平方数，那么a的最小值是________．先将1016分解质因数：，由于是一个完全平方数，所以至少为，故a最小为．恰是自然数b的平方数，a的最小值是。，要使是某个自然数的平方，必须使各个不同质因数的个数为偶数，